{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Stay in the Same Place After Some Steps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #停在原地的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个长度为 <code>arrLen</code> 的数组，开始有一个指针在索引 <code>0</code> 处。</p>\n",
    "\n",
    "<p>每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。</p>\n",
    "\n",
    "<p>给你两个整数 <code>steps</code> 和 <code>arrLen</code> ，请你计算并返回：在恰好执行 <code>steps</code> 次操作以后，指针仍然指向索引 <code>0</code> 处的方案数。</p>\n",
    "\n",
    "<p>由于答案可能会很大，请返回方案数 <strong>模</strong> <code>10^9 + 7</code> 后的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>steps = 3, arrLen = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>3 步后，总共有 4 种不同的方法可以停在索引 0 处。\n",
    "向右，向左，不动\n",
    "不动，向右，向左\n",
    "向右，不动，向左\n",
    "不动，不动，不动\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例  2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>steps = 2, arrLen = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>2 步后，总共有 2 种不同的方法可以停在索引 0 处。\n",
    "向右，向左\n",
    "不动，不动\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>steps = 4, arrLen = 2\n",
    "<strong>输出：</strong>8\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= steps <= 500</code></li>\n",
    "\t<li><code>1 <= arrLen <= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-stay-in-the-same-place-after-some-steps](https://leetcode.cn/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-stay-in-the-same-place-after-some-steps](https://leetcode.cn/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n2', '2\\n4', '4\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(target)\n",
    "        m, l = len(words), len(words[0])\n",
    "\n",
    "        if l < n:\n",
    "            return 0\n",
    "        \n",
    "        freq = [[0] * 26 for _ in range(l)]\n",
    "\n",
    "        def str_idx(x:str):\n",
    "            return ord(x) - ord('a')\n",
    "\n",
    "        for i in range(l):\n",
    "            for j in range(m):\n",
    "                ch = str_idx(words[j][i])\n",
    "                freq[i][ch] += 1\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        f[0] = 1\n",
    "        # f[0] = freq[0][str_idx(target[0])]\n",
    "\n",
    "        for i in range(0, l):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] += f[j-1] * freq[i][str_idx(target[j-1])]\n",
    "                f[j] %= MOD\n",
    "\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        def dfs(dp, cnt, target, i, j, n, m):\n",
    "            if j == m:\n",
    "                return 1\n",
    "            if n - i < m - j:\n",
    "                return 0\n",
    "            if dp[i][j] != -1:\n",
    "                return dp[i][j]\n",
    "            \n",
    "            val = cnt[i][ord(target[j]) - ord('a')] * dfs(dp, cnt, target, i + 1, j + 1, n, m)\n",
    "            val += dfs(dp, cnt, target, i + 1, j, n, m)\n",
    "            val %= mod\n",
    "            dp[i][j] = val\n",
    "            return val\n",
    "        \n",
    "        n = len(words[0])\n",
    "        cnt = [[0] * 26 for _ in range(n)]\n",
    "        for s in words:\n",
    "            for i in range(n):\n",
    "                cnt[i][ord(s[i]) - ord('a')] += 1\n",
    "        \n",
    "        m = len(target)\n",
    "        dp = [[-1] * m for _ in range(n)]\n",
    "        return dfs(dp, cnt, target, 0, 0, n, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "_MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        l_w, l_t = len(words[0]), len(target)\n",
    "        if l_t > l_w:\n",
    "            return 0\n",
    "        cnts = [Counter([w[i] for w in words]) for i in range(l_w)]\n",
    "        f = [[1 for _ in range(l_w)]]\n",
    "        for i in range(1, l_t + 1):\n",
    "            f.append([(f[i - 1][0] * cnts[i - 1][target[i - 1]]) % _MOD])\n",
    "            for j in range(1, l_w - i + 1):\n",
    "                f[i].append((f[i - 1][j] * cnts[i + j - 1][target[i - 1]] + f[i][j - 1]) % _MOD)\n",
    "        return f[l_t][l_w - l_t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(words), len(target)\n",
    "        l = len(words[0])\n",
    "\n",
    "        # Count of each character in each position of words\n",
    "        counts = [[0] * 26 for _ in range(l)]\n",
    "        for word in words:\n",
    "            for i, c in enumerate(word):\n",
    "                counts[i][ord(c) - ord('a')] += 1\n",
    "\n",
    "        # DP array initialization\n",
    "        dp = [[0] * l for _ in range(n)]\n",
    "        dp[0][0] = counts[0][ord(target[0]) - ord('a')]\n",
    "\n",
    "        # DP transition\n",
    "        for j in range(1, l):\n",
    "            dp[0][j] = dp[0][j - 1] + counts[j][ord(target[0]) - ord('a')]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, l):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * counts[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        return dp[n - 1][l - 1]\n",
    "\n",
    "\n",
    "        # 题目意思：words里面选取的顺序并不重要，但是我们选取的第几个字母是需要单调递增的一个特点\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 计算字符在每个位置的频率\n",
    "        freq = [[0] * 26 for _ in range(len(words[0]))]\n",
    "        for word in words:\n",
    "            for j, char in enumerate(word):\n",
    "                freq[j][ord(char) - ord('a')] += 1\n",
    "\n",
    "        # 初始化动态规划数组\n",
    "        m, n = len(target), len(words[0])\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for j in range(n + 1):\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        # 动态规划计算\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * freq[j - 1][ord(target[i - 1]) - ord('a')]\n",
    "                dp[i][j] %= mod\n",
    "\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(words), len(target)\n",
    "        l = len(words[0])\n",
    "\n",
    "        # Count of each character in each position of words\n",
    "        counts = [[0] * 26 for _ in range(l)]\n",
    "        for word in words:\n",
    "            for i, c in enumerate(word):\n",
    "                counts[i][ord(c) - ord('a')] += 1\n",
    "\n",
    "        # DP array initialization\n",
    "        dp = [[0] * l for _ in range(n)]\n",
    "        dp[0][0] = counts[0][ord(target[0]) - ord('a')]\n",
    "\n",
    "        # DP transition\n",
    "        for j in range(1, l):\n",
    "            dp[0][j] = dp[0][j - 1] + counts[j][ord(target[0]) - ord('a')]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, l):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * counts[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        return dp[n - 1][l - 1]\n",
    "\n",
    "        # # Test cases\n",
    "        # words1 = [\"acca\",\"bbbb\",\"caca\"]\n",
    "        # target1 = \"aba\"\n",
    "        # print(numWays(words1, target\n",
    "\n",
    "\n",
    "        # 题目意思：words里面选取的顺序并不重要，但是我们选取的第几个字母是需要单调递增的一个特点\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "        dp[0][0] = freq[0][ord(target[0]) - ord('a')]\n",
    "        for j in range(1,m):\n",
    "            dp[0][j] += dp[0][j - 1] + freq[j][ord(target[0]) - ord('a')]\n",
    "        for i in range(1,n):\n",
    "            idx = ord(target[i]) - ord('a')\n",
    "            for j in range(i,m):\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n -1][m - 1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] 字典中前j个字符与target中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(i,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(1,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n,m = len(words),len(words[0])\n",
    "        t = len(target)\n",
    "        if m<t: return 0\n",
    "        cot = [Counter([e[i] for e in words]) for i in range(m)]\n",
    "        # dp[i][j]表示用words[i:]组成target[j:]的方案数\n",
    "        dp = [[0]*t for _ in range(m)]\n",
    "        dp[m-1][t-1] = 0 if target[-1] not in cot[m-1] else cot[m-1][target[-1]]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            dp[i][t-1] = cot[i][target[t-1]] + dp[i+1][t-1]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            for j in range(t-2, -1, -1):\n",
    "                dp[i][j] = dp[i+1][j] + cot[i][target[j]]*dp[i+1][j+1]\n",
    "                dp[i][j]%=MOD\n",
    "        return dp[0][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, m = len(target), len(words[0])\n",
    "        count = [[0] * 26 for _ in range(m)]  # count[i][j] 统计每个单词第i个字母的ord是j的数目\n",
    "        for i in range(m):\n",
    "            for w in words:\n",
    "                count[i][ord(w[i]) - ord('a')] += 1\n",
    "        dp = [[0] * m for _ in range(n)]  # dp[i][j] 表示由每个单词的前j个字母，组成target的前i个字母的所有可能\n",
    "        dp[0][0] = sum(1 for w in words if w[0] == target[0])\n",
    "        for i in range(n):\n",
    "            for j in range(i, m):  # i <= j\n",
    "                if j == 0 == i: continue\n",
    "                if i == 0:\n",
    "                    dp[i][j] = dp[i][j - 1] + count[j][ord(target[0]) - ord('a')]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * count[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] 字典中前j个字符与target中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(i,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            dp[0][i] = 1\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(1,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        m,n = len(words),len(words[0])\n",
    "        k = len(target)\n",
    "        ct = [Counter() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ct[i][words[j][i]] += 1\n",
    "        @cache\n",
    "        def f(x, p):\n",
    "            if n - x < k - p:\n",
    "                return 0\n",
    "            if p == k:\n",
    "                return 1\n",
    "            r = 0\n",
    "            if target[p] in ct[x]:\n",
    "                r = (r + ct[x][target[p]] * f(x+1, p+1)) % mod\n",
    "            r = (r + f(x+1, p)) % mod\n",
    "\n",
    "            return r\n",
    "        ans = f(0, 0)\n",
    "        f.cache_clear()\n",
    "        return ans\n",
    "                \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        m,n = len(words),len(words[0])\n",
    "        k = len(target)\n",
    "        ct = [Counter() for _ in range(n)]\n",
    "        # ct[i] 表示第i列的字母以及对应的个数\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ct[i][words[j][i]] += 1\n",
    "        @cache\n",
    "        def f(x, p):\n",
    "            if n - x < k - p:\n",
    "                return 0\n",
    "            if p == k:\n",
    "                return 1\n",
    "            r = 0\n",
    "            # 可以选择第x列作为target[p]\n",
    "            if target[p] in ct[x]:\n",
    "                r = (r + ct[x][target[p]] * f(x+1, p+1)) % mod\n",
    "            # 不选择第x列作为target[p]\n",
    "            r = (r + f(x+1, p)) % mod\n",
    "            return r\n",
    "        ans = f(0, 0)\n",
    "        f.cache_clear()\n",
    "        return ans\n",
    "                \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# []\n",
    "# [0 => a, b, c]\n",
    "# [1 => c, b, a]\n",
    "# [2 => c, b]\n",
    "# [3 => a, b]\n",
    "# dp[i][j] = dp[i-1][j-1] * pre[i][target[j]] + dp[i-1][j]\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        words_length = len(words[0])\n",
    "        target_length = len(target)\n",
    "        graph = [collections.defaultdict(int) for _ in range(words_length)]\n",
    "        for word in words:\n",
    "            for idx in range(words_length):\n",
    "                graph[idx][word[idx]] += 1\n",
    "        \n",
    "        dp = [[0] * target_length for _ in range(words_length)]\n",
    "        dp[0][0] = graph[0][target[0]]\n",
    "        for i in range(1, words_length):\n",
    "            dp[i][0] = graph[i][target[0]] + dp[i-1][0]\n",
    "            for j in range(1, min(i+1, target_length)):\n",
    "                dp[i][j] = dp[i-1][j-1] * graph[i][target[j]] + dp[i-1][j]\n",
    "                dp[i][j] %= 10**9 + 7\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        dct = defaultdict(lambda: defaultdict(int))\n",
    "        n = len(words[0])\n",
    "        for word in words:\n",
    "            for i, w in enumerate(word):\n",
    "                dct[w][i] += 1\n",
    "\n",
    "        m = len(target)\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        dp[0][0] = 1\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(m):\n",
    "            dp[i+1][0] = 0\n",
    "            pre = dp[i][0]\n",
    "            for j in range(n):\n",
    "                c = dct[target[i]][j]\n",
    "                dp[i+1][j+1] = (pre*c) % mod\n",
    "                pre += dp[i][j+1]\n",
    "        return sum(dp[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        m = len(words[0])\n",
    "        n = len(target)\n",
    "        \n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        chars = [defaultdict(int) for _ in range(m)]\n",
    "        for w in words:\n",
    "            for i in range(m):\n",
    "                chars[i][w[i]] += 1\n",
    "        \n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = chars[0][target[0]]\n",
    "        for j in range(1,m):\n",
    "            dp[j][0] = dp[j-1][0] + chars[j][target[0]]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(i,m):\n",
    "                dp[j][i] = dp[j-1][i] + dp[j-1][i-1]*chars[j][target[i]]\n",
    "                dp[j][i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(row) for row in zip(*words)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == len(target):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for j in range(k,m):\n",
    "                if m - j < len(target) - i:\n",
    "                    break\n",
    "                if target[i] in cnt[j]:\n",
    "                    ans += cnt[j][target[i]] * dfs(i + 1,j + 1) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(w[i] for w in words) for i in range(m)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == len(target):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for j in range(k,m):\n",
    "                if m - j < len(target) - i:\n",
    "                    break\n",
    "                if target[i] in cnt[j]:\n",
    "                    ans += cnt[j][target[i]] * dfs(i + 1,j + 1) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(row) for row in zip(*words)]\n",
    "        n = len(target)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            if m - k < n - i:\n",
    "                return 0\n",
    "            ans = dfs(i,k + 1)\n",
    "            if target[i] in cnt[k]:\n",
    "                ans += cnt[k][target[i]] * dfs(i + 1,k + 1) % MOD\n",
    "                ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(words),len(words[0])\n",
    "        l = len(target)\n",
    "        g = [Counter() for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                g[j][words[i][j]] += 1\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j == l:  return 1\n",
    "            elif n - i < l - j: return 0\n",
    "            if not g[i][target[j]]: return dfs(i + 1, j)\n",
    "            return (dfs(i + 1, j) + g[i][target[j]] * dfs(i + 1, j + 1)) % MOD\n",
    "        return dfs(0,0)\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD #dp[i-1][j-1],j-1需要大于0\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]的匹配完结果数\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(words), len(words[0])\n",
    "        l = len(target)\n",
    "        d = [{} for i in range(n)]#哈希表数组\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c = words[i][j]\n",
    "                d[j][c] = d[j].get(c, 0) + 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):#words字符下标，target字符下标\n",
    "            if j == l:#target遍历完，可行\n",
    "                return 1\n",
    "            elif n - i < l - j:#words中的剩余字符数量小于target的剩余字符数量，方案不可行\n",
    "                return 0\n",
    "            if target[j] not in d[i]:#如果不存在哈希表中\n",
    "                return dfs(i + 1, j)\n",
    "            return (dfs(i + 1, j) + d[i][target[j]] * dfs(i + 1, j + 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          if len(target) - i > n - j:\n",
    "             return 0\n",
    "          return (dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)) % MOD\n",
    "       n = len(words[0])\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words)\n",
    "        p = len(words[0])\n",
    "\n",
    "        cnt = [[0] * 26 for _ in range(p)]\n",
    "        for i in range(m):\n",
    "            for j in range(p):\n",
    "                cnt[j][ord(words[i][j]) - ord('a')] += 1\n",
    "        \n",
    "        @cache\n",
    "        def compute(i,j):\n",
    "            if j == n:\n",
    "                return 1\n",
    "            if p - i < n - j:\n",
    "                return 0\n",
    "            \n",
    "            return (compute(i+1,j) + compute(i+1,j+1)*cnt[i][ord(target[j])-ord('a')])%MOD\n",
    "\n",
    "        return compute(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n, m = len(target), len(words[0])\n",
    "        rec = [[0] * 26 for _ in range(m)]\n",
    "        for w in words:\n",
    "            for i in range(m):\n",
    "                rec[i][ord(w[i]) - ord('a')] += 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for k in range(i, j + 1):\n",
    "                if rec[k][ord(target[i]) - ord('a')]:\n",
    "                    res += rec[k][ord(target[i]) - ord('a')] * dfs(i - 1, k - 1)\n",
    "                    res %= MOD\n",
    "            return res\n",
    "        return dfs(n - 1, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words[0])\n",
    "        MOD = 10 ** 9 + 7\n",
    "        d = [[0] * 26 for _ in range(n)]\n",
    "        for i in words:\n",
    "            for j,c in enumerate(i):\n",
    "                d[j][ord(c) - 97] += 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(m,k):\n",
    "            mval = ord(target[m-1]) - 97\n",
    "            if m == 1:\n",
    "                return d[k][mval]\n",
    "            if k+1 < m:\n",
    "                return 0\n",
    "            \n",
    "            c = 0\n",
    "            for i in range(m-2, k):\n",
    "                c = (c + d[k][mval] * dp(m-1,i)) % MOD\n",
    "            # print(m,k,c, mval, d[k][mval])\n",
    "            return c\n",
    "        return sum([dp(len(target), i) for i in range(n)]) % MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        @cache\n",
    "        def dfs(idx,k) -> int:\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            num = ord(target[idx]) - ord('a')\n",
    "            for i in range(k,m):\n",
    "                if freq[i][num]:\n",
    "                    res += freq[i][num] * dfs(idx + 1,i + 1) % MOD\n",
    "                if m - i < n - idx:\n",
    "                    break\n",
    "            return res % MOD\n",
    "        return dfs(0,0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def build(self, i, k):\n",
    "        if self.l-k < self.t-i:\n",
    "            return 0\n",
    "\n",
    "        if i == self.t:\n",
    "            return 1\n",
    "\n",
    "        if i*(self.l+1)+k in self.d:\n",
    "            return self.d[i*(self.l+1)+k]\n",
    "        \n",
    "        r = self.rec[k][ord(self.target[i])-ord(\"a\")]*self.build(i+1, k+1) + self.build(i, k+1)\n",
    "        self.d[i*(self.l+1)+k] = r\n",
    "        return r\n",
    "\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words)\n",
    "        self.t = t = len(target)\n",
    "        self.target = target\n",
    "        self.l = l = len(words[0])\n",
    "        self.rec = rec = [[0]*26 for _ in range(l)]\n",
    "        for i in range(n):\n",
    "            for j in range(l):\n",
    "                rec[j][ord(words[i][j])-ord(\"a\")] += 1\n",
    "\n",
    "        self.d = {}\n",
    "        return self.build(0, 0) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        cts = []\n",
    "        for i in range(len(words[0])):\n",
    "            cts.append(collections.Counter(words[j][i] for j in range(len(words))))\n",
    "            \n",
    "        n = len(cts)\n",
    "                    \n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, t):\n",
    "            if len(t) > n - cur:\n",
    "                return 0\n",
    "                \n",
    "            if not t:\n",
    "                return 1\n",
    "                \n",
    "            return (dfs(cur+1, t) + cts[cur][t[0]] * dfs(cur+1, t[1:])) % (10**9 + 7)\n",
    "        \n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1) % mod\n",
    "                res %= mod\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        ans = 0\n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        pos = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, w):\n",
    "            if w == len(target): return 1\n",
    "            if p == n: return 0\n",
    "            res = dfs(p + 1, w)\n",
    "            if target[w] in pos[p]: \n",
    "                res = (res + dfs(p + 1, w + 1) * pos[p][target[w]]) % MOD\n",
    "            return res\n",
    "        return dfs(0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays1(self, words: List[str], target: str) -> int:\n",
    "        n=len(words[0])\n",
    "        m=len(words)\n",
    "        dic_lst=[Counter([words[i][k] for i in range(m)]) for k in range(n)]\n",
    "        t=len(target)\n",
    "        dp=[[0]*t for i in range(n)]\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            if target[0] in dic_lst[i]:\n",
    "                cur+=dic_lst[i][target[0]]\n",
    "            dp[i][0]=cur\n",
    "        for i in range(1,n):\n",
    "            for k in range(1,t):\n",
    "                if target[k] in dic_lst[i]:\n",
    "                    dp[i][k]=dic_lst[i][target[k]]*dp[i-1][k-1]+dp[i-1][k]\n",
    "                else:\n",
    "                    dp[i][k]=dp[i-1][k]\n",
    "        return dp[-1][-1]%(10**9+7)\n",
    "\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          return (dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)) % MOD\n",
    "       n = len(words[0])\n",
    "       if len(target) > n:\n",
    "          return 0\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          res = dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)\n",
    "          res %= MOD\n",
    "          return res\n",
    "         #  if cnts[j][ord(target[i]) - ord('0')] > 0:\n",
    "         #     res += cnts[j][ord(target[i]) - ord('0')] * dfs(i + 1, j + 1)\n",
    "          \n",
    "       n = len(words[0])\n",
    "       if len(target) > n:\n",
    "          return 0\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        lw, ls = len(words), len(words[0])\n",
    "        lt = len(target)\n",
    "        dic = [[0]*26 for _ in range(ls)]\n",
    "\n",
    "        for i in range(ls):\n",
    "            for j in range(lw):\n",
    "                dic[i][(ord(words[j][i]) & 31) - 1] += 1\n",
    "\n",
    "        @cache\n",
    "        def fun(nows, nowt):\n",
    "            if nowt == lt:\n",
    "                return 1\n",
    "            if nows == ls:\n",
    "                return 0\n",
    "            return dic[nows][(ord(target[nowt]) & 31) - 1]*fun(nows+1, nowt+1) + fun(nows+1, nowt)\n",
    "        \n",
    "        return fun(0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        n = len(words[0])\n",
    "        m = len(words)\n",
    "        dic_lst = [Counter([words[i][k] for i in range(m)]) for k in range(n)]\n",
    "        t = len(target)\n",
    "        dp = [[0] * t for i in range(n)]\n",
    "        cur = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if target[0] in dic_lst[i]:\n",
    "                cur += dic_lst[i][target[0]]\n",
    "            dp[i][0] = cur\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for k in range(1, t):\n",
    "                if target[k] in dic_lst[i]:\n",
    "                    dp[i][k] = dic_lst[i][target[k]] * dp[i-1][k-1] + dp[i-1][k]\n",
    "                else:\n",
    "                    dp[i][k] = dp[i-1][k]\n",
    "        \n",
    "        return dp[-1][-1] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        lw, ls = len(words), len(words[0])\n",
    "        lt = len(target)\n",
    "        dic = [[0]*26 for _ in range(ls)]\n",
    "\n",
    "        for i in range(ls):\n",
    "            for j in range(lw):\n",
    "                dic[i][(ord(words[j][i]) & 31) - 1] += 1\n",
    "        \n",
    "        dp = [[0]*lt + [1] for _ in range(ls+1)]\n",
    "        for nowt in range(lt-1, -1, -1):\n",
    "            for nows in range(ls-1, -1, -1):\n",
    "                dp[nows][nowt] = dic[nows][(ord(target[nowt]) & 31) - 1]*dp[nows+1][nowt+1] + dp[nows+1][nowt]\n",
    "        return dp[0][0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(target), len(words[0])\n",
    "        word_chars = []\n",
    "        for i in range(n):\n",
    "            word_chars.append(collections.Counter(word[i] for word in words))\n",
    "        \n",
    "        # dp[i][j] = # of ways to form target[:i] using words[:j]\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(n+1): dp[0][i] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i+1][j+1] = word_chars[j][target[i]] * dp[i][j] + dp[i+1][j]\n",
    "\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n, t = len(words), len(words[0]), len(target)\n",
    "        d = [Counter([x[k] for x in words]) for k in range(n)]\n",
    "        dp = [[0] * t for _ in range(n)]\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            x = target[0] \n",
    "            if x in d[i]:\n",
    "                cur += d[i][x]\n",
    "            dp[i][0] = cur\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, t):\n",
    "                c = target[j]\n",
    "                if c in d[i]:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * d[i][c]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        l = len(words)\n",
    "        dp = [[0 for _ in range(m)] for __ in range(n)]\n",
    "        coef=[Counter([words[i][k] for i in range(l)]) for k in range(n)]\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur_s = target[0]\n",
    "            if cur_s in coef[i]:\n",
    "                cur += coef[i][cur_s]\n",
    "            dp[i][0] = cur\n",
    "        for t in range(1,m):\n",
    "            cur_s = target[t]\n",
    "            for i in range(1,n):\n",
    "                if cur_s in coef[i]:\n",
    "                    dp[i][t] = coef[i][cur_s]*dp[i-1][t-1] + dp[i-1][t]\n",
    "                \n",
    "                else:\n",
    "                    dp[i][t] = dp[i-1][t]\n",
    "        \n",
    "        return int(dp[-1][-1] % (10**9 + 7))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n1 = len(words[0])\n",
    "        cnt = []\n",
    "        for i in range(n1):\n",
    "            dict_tmp = {}\n",
    "            for k in range(26):\n",
    "                dict_tmp[chr(97+k)] = 0\n",
    "            for j in range(len(words)):\n",
    "                dict_tmp[words[j][i]] += 1\n",
    "                    # dict_tmp[words[j][i]] % mod\n",
    "            cnt.append(dict_tmp)\n",
    "        # print(words)\n",
    "        # print(target)\n",
    "        # print(cnt)\n",
    "        dp = [[0 for _ in range(len(target)+1)] for _ in range(n1+1)]\n",
    "\n",
    "        # dp[i][j]: 第i位词典字符起，target从第j个开始到最后, i, j 从第0个开始计数\n",
    "        # dp[i][j] = dp[i+1]dp[j] + dp[i+1]dp[j+1] * cnt[i-1][target[j-1]]\n",
    "        dp[n1-1][len(target)-1] = cnt[n1 - 1][target[-1]]\n",
    "        # print(dp)\n",
    "        for i in range(n1-1, -1, -1):\n",
    "            dp[i][len(target)-1] = cnt[i][target[-1]] + dp[i+1][len(target)-1]\n",
    "            # dp[i][len(target)-1] %= mod\n",
    "        # print(dp)\n",
    "        for i in range(n1-1, -1, -1):\n",
    "            # for j in range(1, len(target)+1):\n",
    "            for j in range(len(target)-2, -1, -1):\n",
    "                dp[i][j] = dp[i+1][j] + dp[i+1][j+1] * cnt[i][target[j]]\n",
    "                # dp[i][j] %= mod\n",
    "        # print(dp)\n",
    "        return dp[0][0] % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        d = defaultdict(lambda :0)\n",
    "        for w in words:\n",
    "            for i,x in enumerate(w):\n",
    "                d[(i,x)]+=1\n",
    "        \n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        @cache \n",
    "        def f(x,y):\n",
    "            if x >= n:\n",
    "                return 0\n",
    "            if y == m-1:\n",
    "                return (d[(x,target[y])] + f(x+1, y)) % mod\n",
    "            return (d[(x,target[y])] * f(x+1,y+1) + f(x+1,y)) % mod\n",
    "            \n",
    "        return f(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        o = sum(1 for c in s if c == '1')\n",
    "        if o % 3:\n",
    "            return 0\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        o //= 3\n",
    "        if o == 0:\n",
    "            return ((n - 2) * (n - 1)) // 2 % mod\n",
    "        l, r = 0, n - 1\n",
    "        sl, sr = 0, 0\n",
    "        while sl < o:\n",
    "            sl += int(s[l])\n",
    "            l += 1\n",
    "        while sr < o:\n",
    "            sr += int(s[r])\n",
    "            r -= 1\n",
    "        p1, p2 = 1, 1\n",
    "        while s[l] == '0':\n",
    "            p1 += 1\n",
    "            l += 1\n",
    "        while s[r] == '0':\n",
    "            p2 += 1\n",
    "            r -= 1\n",
    "        return (p1 * p2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        \n",
    "        # 计算 '1' 的总数\n",
    "        ones_count = s.count('1')\n",
    "        \n",
    "        # 如果 '1' 的总数不能被3整除，无法分割成三个部分\n",
    "        if ones_count % 3 != 0:\n",
    "            return 0\n",
    "        \n",
    "        # 如果没有 '1'，可以选择分割点的方式为 C(n-2, 2) 种\n",
    "        if ones_count == 0:\n",
    "            n = len(s)\n",
    "            return ((n - 2) * (n - 1) // 2) % MOD\n",
    "        \n",
    "        # 计算每个部分 '1' 的数量\n",
    "        ones_per_part = ones_count // 3\n",
    "        \n",
    "        # 初始化变量\n",
    "        first_cut, second_cut = 0, 0\n",
    "        \n",
    "        # 找到第一个分割点\n",
    "        count = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                count += 1\n",
    "            if count == ones_per_part:\n",
    "                first_cut = i\n",
    "                break\n",
    "        \n",
    "        # 找到第二个分割点\n",
    "        count = 0\n",
    "        for i in range(first_cut + 1, len(s)):\n",
    "            if s[i] == '1':\n",
    "                count += 1\n",
    "            if count == ones_per_part:\n",
    "                second_cut = i\n",
    "                break\n",
    "        \n",
    "        # 计算两侧零的个数\n",
    "        zero_count_left = 0\n",
    "        zero_count_mid = 0\n",
    "        \n",
    "        for i in range(first_cut + 1,len(s)):\n",
    "            if s[i] == '0':\n",
    "                zero_count_mid += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(second_cut + 1, len(s)):\n",
    "            if s[i] == '1':\n",
    "                break\n",
    "            count += 1\n",
    "        \n",
    "        zero_count_right = count\n",
    "        \n",
    "        return ((zero_count_mid + 1) * (zero_count_right + 1)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = s.count('1')\n",
    "        # 不是3的倍数，不可能分割\n",
    "        if cnt % 3:    \n",
    "            return 0\n",
    "        # 只有0，相当于从长度-1中选2个切割点\n",
    "        if cnt == 0:\n",
    "            return comb(len(s) - 1, 2) % (10 ** 9 + 7)\n",
    "        \n",
    "        part1 = cnt // 3\n",
    "        part2 = part1 << 1\n",
    "        cnt1 = cnt2 = 1\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                cnt += 1\n",
    "            elif cnt == part1:\n",
    "                cnt1 += 1\n",
    "            elif cnt == part2:\n",
    "                cnt2 += 1\n",
    "        \n",
    "        \n",
    "        return cnt1 * cnt2 % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        num = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                num += 1\n",
    "        if num == 0:\n",
    "            return ((n-2)*(n-1)//2)%1000000007\n",
    "        if num%3 != 0:\n",
    "            return 0\n",
    "        tmp = num//3\n",
    "        i1,i2,i3,i4 = 0,0,0,0\n",
    "        count_1 = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                count_1 += 1\n",
    "                if count_1 == tmp:\n",
    "                    i1 = i\n",
    "                if count_1 == (tmp + 1):\n",
    "                    i2 = i\n",
    "                if count_1 == (tmp*2):\n",
    "                    i3 = i\n",
    "                if count_1 == (tmp*2+1):\n",
    "                    i4 = i\n",
    "        return ((i2-i1)*(i4-i3))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones = 0\n",
    "        for c in s:\n",
    "            if(c == '1'):\n",
    "                ones += 1\n",
    "        if(ones % 3 != 0):\n",
    "            return 0\n",
    "        if(ones == 0):\n",
    "            return (n-1)*(n-2)//2 % M\n",
    "        ones_cnt = ones // 3\n",
    "        pos = [[-1,-1],[-1,-1],[-1,-1]]\n",
    "        pi = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(s)):\n",
    "            if(s[i] == '1'):\n",
    "                if(tmp == 0):\n",
    "                    pos[pi][0] = i\n",
    "                tmp += 1\n",
    "            if(tmp == ones_cnt):\n",
    "                pos[pi][1] = i \n",
    "                tmp = 0\n",
    "                pi += 1\n",
    "        result = (pos[1][0] - pos[0][1])*(pos[2][0]-pos[1][1])\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = s.count(\"1\")\n",
    "        if n%3!=0:\n",
    "            return 0\n",
    "        if n==0:\n",
    "            return comb(len(s)-1,2)%(10**9+7)\n",
    "        x = n//3\n",
    "        t = 0\n",
    "        a = -2\n",
    "        ans = []\n",
    "        while a!=-1:\n",
    "            a = -1 if a==-2 else a\n",
    "            a = s.find(\"1\",a+1)\n",
    "            if t==x-1:\n",
    "                ans.append(a)\n",
    "            if t==x:\n",
    "                ans.append(a)\n",
    "            if t==x*2-1:\n",
    "                ans.append(a)\n",
    "            if t==x*2:\n",
    "                ans.append(a)\n",
    "            t += 1\n",
    "        return ((ans[1]-ans[0])*(ans[3]-ans[2])) %(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n,m=len(s),s.count('1')\n",
    "        if(m%3!=0):return 0\n",
    "        if(m==0):return (n-1)*(n-2)//2%1000000007\n",
    "        m/=3;x,y,z=0,0,0\n",
    "        for i in range(n):\n",
    "            if(s[i]=='1'):\n",
    "                z+=1\n",
    "                if(z==m):x=i;break\n",
    "        for i in range(x+1,n):\n",
    "            if(s[i]=='1'):x,y,z=i-x,i,0;break\n",
    "        for i in range(y,n):\n",
    "            if(s[i]=='1'):\n",
    "                z+=1\n",
    "                if(z==m):y=i;break\n",
    "        for i in range(y+1,n):\n",
    "            if(s[i]=='1'):y=i-y;break\n",
    "        return x*y%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        all = Counter(s)['1']\n",
    "        if all%3 != 0:\n",
    "            return 0\n",
    "        standard = all//3\n",
    "        length = len(s)\n",
    "        if all == 0:\n",
    "            return int((length-1)*(length-2)/2) % 1000000007\n",
    "        start_index = 0\n",
    "        end_index = 0\n",
    "        index = -1\n",
    "        count = 0\n",
    "        while -index<length:\n",
    "            if s[index] == '1':\n",
    "                count += 1\n",
    "                if count == standard:\n",
    "                    end_index = index\n",
    "                if count > standard:\n",
    "                    start_index = index\n",
    "                    break\n",
    "            index -= 1\n",
    "        ans = end_index-start_index\n",
    "        start_index = end_index = index = count = 0\n",
    "        while index<length:\n",
    "            if s[index] == '1':\n",
    "                count += 1\n",
    "                if count == standard:\n",
    "                    start_index = index\n",
    "                if count > standard:\n",
    "                    end_index = index\n",
    "                    break\n",
    "            index += 1\n",
    "        ans *= (end_index-start_index)\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        #只分成3个字符串\n",
    "        #s中的1 平均分配给s1,s2,s3\n",
    "\n",
    "        #先统计一共有几个1\n",
    "        l = len(s)\n",
    "        sum_1 = 0\n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                sum_1 += 1\n",
    "        print('s中一共有%d个1'%sum_1)\n",
    "\n",
    "        if sum_1%3 != 0:\n",
    "            return 0\n",
    "        elif sum_1 == 0:\n",
    "            res = 0\n",
    "            for i in range(l-2):\n",
    "                res += l - 2 - i\n",
    "            return res%(10**9+7)\n",
    "        else:\n",
    "            n = sum_1//3 #每个子字符串中'1'的数量\n",
    "        \n",
    "        #由于s1 + s2 + s3 = s 所以'1'的分配是有顺序的 \n",
    "        #前n个1给s1，中间n个1给s2，最好n个1给s3 (假设n>0)\n",
    "\n",
    "        #观察s1,s2,s3交互的边界\n",
    "        Dict = {n:0,n+1:0,2*n:0,2*n+1:0}\n",
    "        count = 0\n",
    "        index = 0\n",
    "        #print([n,n+1,2*n,2*n+1])\n",
    "        for i in s:\n",
    "            if i=='1':\n",
    "                count += 1\n",
    "                #print(count)\n",
    "                if count in Dict:\n",
    "                    Dict[count] = index\n",
    "            index += 1\n",
    "        print(Dict)\n",
    "        #print(49001**2)\n",
    "        return (Dict[n+1]-Dict[n])*(Dict[2*n+1]-Dict[2*n])%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        count_1 = s.count('1')\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        if count_1 % 3 != 0:\n",
    "            return 0\n",
    "        if count_1 == 0:\n",
    "            return (n - 2) * (n - 1) // 2 % mod\n",
    "        gap1 = 0\n",
    "        gap2 = 0\n",
    "        total_1 = 0\n",
    "        # gap is the count for zeros between two chunks of ones\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                total_1 += 1\n",
    "            if c == '0':\n",
    "                if total_1 == count_1 // 3:\n",
    "                    gap1 += 1\n",
    "                if total_1 == count_1 // 3 * 2:\n",
    "                    gap2 += 1\n",
    "        return (gap1 + 1) * (gap2 + 1) % mod                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones = 0\n",
    "        for c in s:\n",
    "            if(c == '1'):\n",
    "                ones += 1\n",
    "        if(ones % 3 != 0):\n",
    "            return 0\n",
    "        if(ones == 0):\n",
    "            return (n-1)*(n-2)//2 % M\n",
    "        ones_cnt = ones // 3\n",
    "        pos = [[-1,-1],[-1,-1],[-1,-1]]\n",
    "        pi = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(s)):\n",
    "            if(s[i] == '1'):\n",
    "                if(tmp == 0):\n",
    "                    pos[pi][0] = i\n",
    "                tmp += 1\n",
    "            if(tmp == ones_cnt):\n",
    "                pos[pi][1] = i \n",
    "                tmp = 0\n",
    "                pi += 1\n",
    "        result = (pos[1][0] - pos[0][1])*(pos[2][0]-pos[1][1])\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numWays(self, s: str) -> int:\r\n",
    "        #统计1的个数\r\n",
    "        #如果1的个数不能被3整除，直接返回0\r\n",
    "        cnt = s.count('1')\r\n",
    "        if cnt % 3 != 0:\r\n",
    "            return 0\r\n",
    "        #如果1的个数为0，那么返回C(n-2, 2)\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        n = len(s)\r\n",
    "        if cnt == 0:\r\n",
    "            return (n - 2) * (n - 1) // 2 % MOD\r\n",
    "        #如果1的个数能被3整除\r\n",
    "        #查找第一段和第二段的1中间有多少个0,n1\r\n",
    "        #查找第二段和第三段的1中间有多少个0,n2\r\n",
    "        #返回n1 * n2 % MOD\r\n",
    "        n1,n2 = 0,0\r\n",
    "        cnt1,cnt2 = 0,0\r\n",
    "        for i in range(n):\r\n",
    "            if s[i] == '1':\r\n",
    "                cnt1 += 1\r\n",
    "            if cnt // 3 <= cnt1 <= cnt // 3 * + 1:\r\n",
    "                n1 += 1\r\n",
    "        for i in range(n-1,-1,-1):\r\n",
    "            if s[i] == '1':\r\n",
    "                cnt2 += 1\r\n",
    "            if cnt // 3 <= cnt2 <= cnt // 3 * + 1:\r\n",
    "                n2 += 1\r\n",
    "        return n1 * n2 % MOD\r\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        x, cnt, f1, f2 = s.count('1'), 0, 0, 0\n",
    "        if x%3: return 0\n",
    "        if x==0: return ((len(s)-1)*(len(s)-2)//2)%1000000007\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='1': cnt += 1\n",
    "            if not f1 and cnt==x//3: f1 = len(s)-i-len(s[i+1:].lstrip('0'))\n",
    "            if cnt==2*x//3: \n",
    "                f2 = len(s)-i-len(s[i+1:].lstrip('0'))\n",
    "                return f1*f2%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "\n",
    "        sum_ = 0\n",
    "\n",
    "        for ss in s:\n",
    "            if ss == '1':\n",
    "                sum_ += 1\n",
    "        \n",
    "        if sum_ % 3 != 0:\n",
    "            return 0\n",
    "\n",
    "        \n",
    "        cnt = sum_ // 3\n",
    "\n",
    "        if cnt == 0:\n",
    "            return ((len(s) - 1) * (len(s) - 2) // 2) % mod\n",
    "\n",
    "        \n",
    "        presum = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                presum += 1\n",
    "                if presum == cnt:\n",
    "                    break\n",
    "        \n",
    "        leftStart = i\n",
    "        i += 1\n",
    "        while i < len(s) and s[i] == '0':\n",
    "            i += 1\n",
    "        \n",
    "        leftEnd = i - 1\n",
    "\n",
    "\n",
    "\n",
    "        suffix = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == '1':\n",
    "                suffix += 1\n",
    "                if suffix == cnt:\n",
    "                    break\n",
    "        \n",
    "        rightEnd = i \n",
    "        i -= 1\n",
    "\n",
    "        while i >= 0 and s[i] == '0':\n",
    "            i -= 1\n",
    "\n",
    "        rightStart = i + 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return (leftEnd - leftStart + 1) * (rightEnd - rightStart + 1) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mod = 10 ** 9 + 7\n",
    "        ones = s.count('1')\n",
    "        if ones % 3:\n",
    "            return 0\n",
    "        if ones == 0:\n",
    "            return comb(n - 1, 2) % mod \n",
    "        per = ones // 3\n",
    "        rec = []\n",
    "        cnt = 0\n",
    "        for i, j in enumerate(s):\n",
    "            if j == '1':\n",
    "                cnt += 1\n",
    "                for k in [per, per + 1, 2 * per, 2 * per + 1]:\n",
    "                    if k == cnt:\n",
    "                        rec.append(i)\n",
    "        ans = (rec[1] - rec[0]) * (rec[3] - rec[2]) % mod \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        cnt = s.count('1')\n",
    "        if cnt % 3:\n",
    "            return 0\n",
    "\n",
    "        if cnt == 0:\n",
    "            n = len(s)\n",
    "            if n < 3:\n",
    "                return 0\n",
    "            \n",
    "            return (n-1) * (n-2) // 2 % MOD\n",
    "\n",
    "\n",
    "        \n",
    "        cnt //= 3\n",
    "        cnt1 = 0\n",
    "        cntPre = 1\n",
    "        cntAfter = 1\n",
    "\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                cnt1 += 1\n",
    "            \n",
    "            if cnt1 == cnt and c == '0':\n",
    "                cntPre += 1\n",
    "            elif cnt1 == cnt * 2 and c == '0':\n",
    "                cntAfter += 1\n",
    "\n",
    "        return cntPre * cntAfter % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numWays(self, s: str) -> int:\r\n",
    "        #统计1的个数\r\n",
    "        #如果1的个数不能被3整除，直接返回0\r\n",
    "        cnt = s.count('1')\r\n",
    "        if cnt % 3 != 0:\r\n",
    "            return 0\r\n",
    "        #如果1的个数为0，那么返回C(n-2, 2)\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        n = len(s)\r\n",
    "        if cnt == 0:\r\n",
    "            return (n - 2) * (n - 1) // 2 % MOD\r\n",
    "        #如果1的个数能被3整除\r\n",
    "        #查找第一段和第二段的1中间有多少个0,n1\r\n",
    "        #查找第二段和第三段的1中间有多少个0,n2\r\n",
    "        #返回n1 * n2 % MOD , n1n2已经加1\r\n",
    "        n1,n2 = 0,0\r\n",
    "        cnt1,cnt2 = 0,0\r\n",
    "        for i in range(n):\r\n",
    "            if s[i] == '1':\r\n",
    "                cnt1 += 1\r\n",
    "            if cnt // 3 <= cnt1 <= cnt // 3 * + 1:\r\n",
    "                n1 += 1\r\n",
    "        for i in range(n-1,-1,-1):\r\n",
    "            if s[i] == '1':\r\n",
    "                cnt2 += 1\r\n",
    "            if cnt // 3 <= cnt2 <= cnt // 3 * + 1:\r\n",
    "                n2 += 1\r\n",
    "        return n1 * n2 % MOD\r\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones = 0\n",
    "        for c in s:\n",
    "            if(c == '1'):\n",
    "                ones += 1\n",
    "        if(ones % 3 != 0):\n",
    "            return 0\n",
    "        if(ones == 0):\n",
    "            return (n-1)*(n-2)//2 % M\n",
    "        ones_cnt = ones // 3\n",
    "        pos = [[-1,-1],[-1,-1],[-1,-1]]\n",
    "        pi = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(s)):\n",
    "            if(s[i] == '1'):\n",
    "                if(tmp == 0):\n",
    "                    pos[pi][0] = i\n",
    "                tmp += 1\n",
    "            if(tmp == ones_cnt):\n",
    "                pos[pi][1] = i \n",
    "                tmp = 0\n",
    "                pi += 1\n",
    "        result = (pos[1][0] - pos[0][1])*(pos[2][0]-pos[1][1])\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(s)\n",
    "        c = s.count('1')\n",
    "        if c % 3 != 0: return 0\n",
    "        a = c // 3\n",
    "        if a == 0:\n",
    "            return ((n - 2) * (n - 1) // 2) % MOD\n",
    "        i1, i2, i3, i4 = 0, 0, 0, 0\n",
    "        cnt = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '1':\n",
    "                cnt += 1\n",
    "                print(i, cnt)\n",
    "                if cnt == a:\n",
    "                    i1 = i\n",
    "                if cnt == a + 1:\n",
    "                    i2 = i\n",
    "                if cnt == 2 * a:\n",
    "                    i3 = i\n",
    "                if cnt == 2 * a + 1:\n",
    "                    i4 = i\n",
    "        # print(i1, i2, i3, i4)\n",
    "        return (i2 - i1) * (i4 - i3) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numWays(self, s: str) -> int:\r\n",
    "        o = sum(1 for c in s if c == '1')\r\n",
    "        if o % 3:\r\n",
    "            return 0\r\n",
    "        mod = 1000000007\r\n",
    "        n = len(s)\r\n",
    "        o //= 3\r\n",
    "        if o == 0:\r\n",
    "            return ((n - 2) * (n - 1)) // 2 % mod\r\n",
    "        l, r = 0, n - 1\r\n",
    "        sl, sr = 0, 0\r\n",
    "        while sl < o:\r\n",
    "            sl += int(s[l])\r\n",
    "            l += 1\r\n",
    "        while sr < o:\r\n",
    "            sr += int(s[r])\r\n",
    "            r -= 1\r\n",
    "        p1, p2 = 1, 1\r\n",
    "        while s[l] == '0':\r\n",
    "            p1 += 1\r\n",
    "            l += 1\r\n",
    "        while s[r] == '0':\r\n",
    "            p2 += 1\r\n",
    "            r -= 1\r\n",
    "        return (p1 * p2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = s.count('1')\n",
    "        if cnt % 3: return 0\n",
    "        if cnt == 0:\n",
    "            return comb(len(s) - 1, 2) % MOD\n",
    "        t = cnt // 3\n",
    "        p = [i for i, x in enumerate(s) if x == '1']\n",
    "        t2 = cnt // 3 * 2\n",
    "        cnt1 = p[t] - p[t - 1]\n",
    "        cnt2 = p[t2] - p[t2 - 1]\n",
    "        return (cnt1 * cnt2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%(10**9+7)        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        # 1的数量必平分，然后统计间隔的0的数量相乘\n",
    "        # 如果全是0的话就看成组合问题\n",
    "        n = len(s)\n",
    "        one_indexs = [k for k,v in enumerate(s) if v=='1']\n",
    "        one_count = len(one_indexs)\n",
    "        if one_count%3!=0 :\n",
    "            return 0\n",
    "        if one_count == 0:\n",
    "            return int((n-1)*(n-2)/2)%(1000000007)\n",
    "        one_need = int(one_count/3) \n",
    "        return ((one_indexs[one_need] - one_indexs[one_need-1]) * (one_indexs[one_need*2] - one_indexs[one_need*2-1]))%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MODULO = 1000000007\n",
    "\n",
    "        ones = list()\n",
    "        n = len(s)\n",
    "        for i, digit in enumerate(s):\n",
    "            if digit == \"1\":\n",
    "                ones.append(i)\n",
    "        \n",
    "        m = len(ones)\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        \n",
    "        if m == 0:\n",
    "            ways = (n - 1) * (n - 2) // 2\n",
    "            return ways % MODULO\n",
    "        else:\n",
    "            index1, index2 = m // 3, m // 3 * 2;\n",
    "            count1 = ones[index1] - ones[index1 - 1]\n",
    "            count2 = ones[index2] - ones[index2 - 1]\n",
    "            ways = count1 * count2\n",
    "            return ways % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = [i for i,n in enumerate(s) if n == '1']\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] == '1':\n",
    "        #         cnt.append(i)\n",
    "        if len(cnt) % 3 != 0:return 0\n",
    "        if len(cnt) == 0:return int(((len(s)-1)*(len(s)-2)//2)%(1000000007))\n",
    "        gap = int(len(cnt) / 3)\n",
    "        return int(((cnt[gap]-cnt[gap-1])*(cnt[gap*2]-cnt[gap*2-1]))%(1000000007))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%1000000007        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%1000000007        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%1000000007\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        ones = list()\n",
    "        for i, c in enumerate(s):\n",
    "            if c == \"1\":\n",
    "                ones.append(i)\n",
    "        m = len(ones)\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        if m == 0:\n",
    "            return ((len(s)-1)*(len(s)-2)//2) % (10**9+7)\n",
    "        else:\n",
    "            index1 = m // 3\n",
    "            index2 = 2 * m // 3\n",
    "            num1 = ones[index1] - ones[index1-1]\n",
    "            num2 = ones[index2] - ones[index2-1]\n",
    "            return (num1 * num2) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(s)\n",
    "        ones = [i for i, num in enumerate(s) if num == \"1\"] \n",
    "        k = len(ones)\n",
    "        if k == 0:\n",
    "            return (n-1)*(n-2)//2%mod \n",
    "\n",
    "        a,b = divmod(k,3)\n",
    "        if b:\n",
    "            return 0\n",
    "\n",
    "        return (ones[a]-ones[a-1])*(ones[a*2]-ones[a*2-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        oneIndex = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(oneIndex)\n",
    "        if k%3:\n",
    "            return 0\n",
    "\n",
    "        n = len(s)\n",
    "        if k==0:\n",
    "            res = (n-1)*(n-2) // 2\n",
    "            return res%1000000007\n",
    "\n",
    "        index1 = k//3\n",
    "        index2 = k//3 * 2\n",
    "        count1 = oneIndex[index1]-oneIndex[index1-1]\n",
    "        count2 = oneIndex[index2]-oneIndex[index2-1]\n",
    "        return count1 * count2 % 1000000007        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        total_1 = 0\n",
    "        list_1 = []\n",
    "        for i in range(length):\n",
    "            if int(s[i]) == 1:\n",
    "                total_1 += 1\n",
    "                list_1.append(i)\n",
    "\n",
    "        if total_1 % 3 != 0:\n",
    "            return 0\n",
    "        if list_1 == []:\n",
    "            return int((math.comb(length-1,2) % (10e8+7)))\n",
    "        ans = (list_1[int(total_1 / 3 - 1)] - list_1[int(total_1 / 3)]) * (list_1[int(total_1 / 3 * 2 - 1)] - \n",
    "                                                                   list_1[int(total_1 / 3 * 2)])\n",
    "        return int(ans % (10e8+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        slist =[]\n",
    "        for idx, st in enumerate(s):\n",
    "            if st == '1':\n",
    "                slist.append(idx)\n",
    "        n = len(slist)\n",
    "\n",
    "        BIGNUM = 1000000007\n",
    "        if n % 3 or len(s) < 3:\n",
    "            return 0\n",
    "\n",
    "        if n == 0:\n",
    "            return ((len(s)-1)*(len(s)-2)//2)%BIGNUM\n",
    "\n",
    "        if n > 0:\n",
    "            ave = len(slist)//3\n",
    "            left0 = slist[ave]-slist[ave-1]\n",
    "            right0 = slist[-ave]-slist[-ave-1]\n",
    "            return (left0*right0)%BIGNUM\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MODULO = 1000000007\n",
    "        n=len(s)\n",
    "        ones=list()\n",
    "        for i,x in enumerate(s):\n",
    "            if x==\"1\":\n",
    "                ones.append(i)\n",
    "        \n",
    "        m=len(ones)\n",
    "\n",
    "        if m%3!=0:\n",
    "            return 0\n",
    "\n",
    "        if m==0:\n",
    "            return ((n-1)*(n-2)//2)%MODULO\n",
    "        else:\n",
    "            index1=m//3\n",
    "            index2=m//3*2\n",
    "            count1=ones[index1]-ones[index1-1]\n",
    "            count2=ones[index2]-ones[index2-1]\n",
    "            ways=count1*count2\n",
    "            return ways%MODULO\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = [i for i,n in enumerate(s) if n == '1']\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] == '1':\n",
    "        #         cnt.append(i)\n",
    "        if len(cnt) % 3 != 0:return 0\n",
    "        if len(cnt) == 0:return int(((len(s)-1)*(len(s)-2)//2)%(1000000007))\n",
    "        gap = int(len(cnt) / 3)\n",
    "        return int(((cnt[gap]-cnt[gap-1])*(cnt[gap*2]-cnt[gap*2-1]))%(1000000007))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MODULO = 1000000007\n",
    "\n",
    "        ones = list()\n",
    "        n = len(s)\n",
    "        for i, digit in enumerate(s):\n",
    "            if digit == \"1\":\n",
    "                ones.append(i)\n",
    "        \n",
    "        m = len(ones)\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        \n",
    "        if m == 0:\n",
    "            ways = (n - 1) * (n - 2) // 2\n",
    "            return ways % MODULO\n",
    "        else:\n",
    "            index1, index2 = m // 3, m // 3 * 2\n",
    "            count1 = ones[index1] - ones[index1 - 1]\n",
    "            count2 = ones[index2] - ones[index2 - 1]\n",
    "            ways = count1 * count2\n",
    "            return ways % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 模拟\n",
    "    def numWays(self, s: str) -> int:\n",
    "        MODULO = 1000000007\n",
    "\n",
    "        ones = list()\n",
    "        n = len(s)\n",
    "        for i, digit in enumerate(s):\n",
    "            if digit == \"1\":\n",
    "                ones.append(i)\n",
    "        \n",
    "        m = len(ones)\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        \n",
    "        if m == 0:\n",
    "            ways = (n - 1) * (n - 2) // 2\n",
    "            return ways % MODULO\n",
    "        else:\n",
    "            index1, index2 = m // 3, m // 3 * 2;\n",
    "            count1 = ones[index1] - ones[index1 - 1]\n",
    "            count2 = ones[index2] - ones[index2 - 1]\n",
    "            ways = count1 * count2\n",
    "            return ways % MODULO\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%1000000007        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                cnt.append(i)\n",
    "        if len(cnt) % 3 != 0:return 0\n",
    "        if len(cnt) == 0:return int(((len(s)-1)*(len(s)-2)//2)%(1000000007))\n",
    "        gap = int(len(cnt) / 3)\n",
    "        return int(((cnt[gap]-cnt[gap-1])*(cnt[gap*2]-cnt[gap*2-1]))%(1000000007))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt=s.count('1')\n",
    "        if cnt%3!=0:\n",
    "            return 0\n",
    "        if cnt==0:\n",
    "            m=len(s)\n",
    "            return int((m-1)*(m-2)/2)%(10**9+7)\n",
    "        pos=[]\n",
    "        k=int(cnt/3)\n",
    "        i=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='1':\n",
    "                pos.append(i)\n",
    "        s_0=pos[k]-pos[k-1]\n",
    "        s_1=pos[2*k]-pos[2*k-1]\n",
    "        return (s_0*s_1)%(10**9+7)\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        news = [i for i,num in enumerate(s) if num=='1']\n",
    "        k = len(news)\n",
    "        if k%3:return 0\n",
    "        if not k:return (len(s)-1)*(len(s)-2)//2%1000000007        \n",
    "        return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        n = len(s)\n",
    "        m = cnt[\"1\"]\n",
    "        if m % 3 != 0:\n",
    "            return 0\n",
    "        if m == 0:\n",
    "            return (n - 1) * (n - 2) // 2 % (10 ** 9 + 7)\n",
    "        else:\n",
    "            count = 0\n",
    "            dic = {}\n",
    "            for i, ch in enumerate(s):\n",
    "                if ch == \"1\":\n",
    "                    count += 1\n",
    "                    dic[count] = i\n",
    "            lst = []\n",
    "            for key, value in dic.items():\n",
    "                if key == m // 3 or key == m // 3 + 1:\n",
    "                    lst.append(value)\n",
    "                if key == 2 * m // 3 or key == 2 * m // 3 + 1:\n",
    "                    lst.append(value)\n",
    "            return (lst[1] - lst[0]) * (lst[3] - lst[2]) %(10 **9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        t = 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                t += 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        if t % 3:\n",
    "            return 0\n",
    "        if t == 0:\n",
    "            return math.comb(n - 1,2) % mod\n",
    "        tmp = -1\n",
    "        tp = 0\n",
    "        s = list(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                tp += 1\n",
    "            if tp == t // 3:\n",
    "                tmp = i\n",
    "                break\n",
    "        \n",
    "        z0 = 1\n",
    "        tmp += 1\n",
    "        while tmp < n and s[tmp] == '0':\n",
    "            z0 += 1\n",
    "            \n",
    "            tmp += 1\n",
    "        tmp = -1\n",
    "        tp = 0\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            if s[i] == '1':\n",
    "                tp += 1\n",
    "            if tp == t // 3:\n",
    "                tmp = i\n",
    "                break\n",
    "        z1 = 1\n",
    "        tmp -= 1\n",
    "        while tmp >= 0 and s[tmp] == '0':\n",
    "            z1 += 1\n",
    "            tmp -= 1\n",
    "        return z0 * z1 % mod\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: str) -> int:\n",
    "        c=s.count('1')\n",
    "        n=len(s)\n",
    "        if c%3 :\n",
    "            return 0\n",
    "        if c==0:\n",
    "            return ((n-1)*(n-2)//2)%(10**9+7)    \n",
    "        r=c/3\n",
    "        k=-1\n",
    "        j=0\n",
    "        s=list(s)\n",
    "        \n",
    "        cur=0\n",
    "        a=[]\n",
    "        for i in range(n):\n",
    "            if s[i]=='1':\n",
    "              if k!=-1:\n",
    "                 a.append(i-k)\n",
    "                 k=-1   \n",
    "              cur+=1\n",
    "            if cur==r:\n",
    "               k=i\n",
    "               cur=0\n",
    "                   \n",
    "        return (a[0]*a[1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        arrLen = min(steps, arrLen - 1)\n",
    "        dp = [0] * (arrLen + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, steps + 1):\n",
    "            temp = [0] * (arrLen + 1)\n",
    "            for j in range(arrLen + 1):\n",
    "                temp[j] += dp[j]\n",
    "                if j + 1 <= arrLen:\n",
    "                    temp[j] += dp[j + 1]\n",
    "                if j - 1 >= 0:\n",
    "                    temp[j] += dp[j - 1]\n",
    "            dp = temp\n",
    "        return dp[0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from time import time\n",
    "import sys\n",
    "sys.setrecursionlimit(10000)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        num = 10 ** 9 + 7\n",
    "        max_len = arrLen if arrLen < steps else steps\n",
    "        # dp = [[0 for j in range(max_len)] for i in range(steps)]\n",
    "        # dp[0][0] = 1\n",
    "        # for s in range(steps):\n",
    "        #     for i in range(max_len):\n",
    "        #         if s > 0:\n",
    "        #             if i == 0:\n",
    "        #                 dp[s][i] = (dp[s - 1][i] + dp[s - 1][i + 1]) % num\n",
    "        #             elif i == max_len - 1:\n",
    "        #                 dp[s][i] = (dp[s - 1][i] + dp[s - 1][i - 1]) % num\n",
    "        #             else:\n",
    "        #                 dp[s][i] = (dp[s - 1][i] + dp[s - 1][i + 1] + dp[s - 1][i - 1]) % num\n",
    "        # return dp[steps - 1][max_len - 1]\n",
    "\n",
    "        @lru_cache(1024 * 2)\n",
    "        def dfs(s, i):\n",
    "            if max_len == 1:\n",
    "                return 1\n",
    "            if s == 0:\n",
    "                if i == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    return (dfs(s - 1, i + 1) + dfs(s - 1, i)) % num\n",
    "                if i == max_len - 1:\n",
    "                    return (dfs(s - 1, i - 1) + dfs(s - 1, i)) % num\n",
    "                return (dfs(s - 1, i + 1) + dfs(s - 1, i) + dfs(s - 1, i - 1)) % num\n",
    "        \n",
    "        return dfs(steps, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        if arrLen == 1: return 1\n",
    "        n = min(arrLen, steps // 2 + 1)\n",
    "        dp = [[0] * n for _ in range(steps + 1)]\n",
    "        dp[0][0] = 1        \n",
    "        for i in range(1, steps + 1):\n",
    "            dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD\n",
    "            dp[i][n-1] = (dp[i-1][n-1] + dp[i-1][n-2]) % MOD\n",
    "            for j in range(1, n-1):\n",
    "                dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j + 1]) % MOD\n",
    "        \n",
    "        return dp[steps][0]\n",
    "\n",
    "        # MOD = 10**9+7\n",
    "        # if arrLen == 1: return 1\n",
    "\n",
    "        # n = min(steps // 2 + 1, arrLen)\n",
    "        # dp = [[0] * n for _ in range(steps + 1)]\n",
    "        # dp[0][0] = 1\n",
    "\n",
    "        # for i in range(1, steps + 1):\n",
    "        #     dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD\n",
    "        #     dp[i][n-1] = (dp[i-1][n-1] + dp[i-1][n-2]) % MOD\n",
    "        #     for j in range(1, n-1):\n",
    "        #         dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1]) % MOD\n",
    "        \n",
    "        # return dp[steps][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        mc = min(arrLen, steps // 2 + 1)\n",
    "        dp = [[0] * mc for _ in range(steps + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, steps + 1):\n",
    "            for j in range(mc):\n",
    "                t1 = dp[i-1][j]\n",
    "                t2 = dp[i-1][j-1] if j >= 1 else 0\n",
    "                t3 = dp[i-1][j+1] if j <= mc - 2 else 0\n",
    "                dp[i][j] = (t1 + t2 + t3) % MOD\n",
    "        return dp[steps][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        #考虑数据范围，在n步骤后停留在[0,n]的方案数目？\n",
    "        n = steps\n",
    "        a = min(arrLen,n//2+1)\n",
    "        Mod = 10**9+7\n",
    "        d = [[0 for _ in range(n+2)] for _ in range(n+1)]\n",
    "        d[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(min(a, i+1)):\n",
    "                \n",
    "                   \n",
    "                    d[i][j]+= d[i-1][j-1] + d[i-1][j] +d[i-1][j+1]\n",
    "                    d[i][j]%=Mod\n",
    "\n",
    "        return d[n][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod=10**9+7\n",
    "        maxnum=min(arrLen-1,steps)\n",
    "        ij=[[0]*(maxnum+1)for x in range(steps+1)]\n",
    "        ij[0][0]=1\n",
    "        for i in range(1,steps+1):\n",
    "            for j in range(maxnum+1):\n",
    "                ij[i][j]=ij[i-1][j]\n",
    "                if (j-1)>=0: ij[i][j]=(ij[i][j]+ij[i-1][j-1])%mod\n",
    "                if (j+1)<=(maxnum): ij[i][j]=(ij[i][j]+ij[i-1][j+1])%mod\n",
    "        return ij[steps][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        #dp[s][i] = dp[s-1][i] + dp[s-1][i+1] + dp[s][i-1]\n",
    "        MOD = 10**9+7\n",
    "        arrLen = min(2*steps,arrLen)\n",
    "        dp = [[0]*arrLen for _ in range(steps+1)]\n",
    "        dp[0][0] = 1\n",
    "        for s in range(1,steps+1):\n",
    "            for i in range(arrLen):\n",
    "                dp[s][i] += dp[s-1][i]\n",
    "                if i+1<arrLen:\n",
    "                    dp[s][i] +=dp[s-1][i+1]\n",
    "                if i-1>=0:\n",
    "                    dp[s][i] +=dp[s-1][i-1]\n",
    "                dp[s][i] = dp[s][i]%MOD\n",
    "        return dp[steps][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        s = min(steps // 2 + 1, arrLen)\n",
    "        dp = [[0] * s for _ in range(steps + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, steps + 1):\n",
    "            for j in range(s):\n",
    "                if j - 1 >= 0:\n",
    "                    dp[i][j] += dp[i - 1][j - 1]\n",
    "                if j + 1 < s:\n",
    "                    dp[i][j] += dp[i - 1][j + 1]\n",
    "                dp[i][j] += dp[i - 1][j]\n",
    "        # print(dp)\n",
    "        return dp[steps][0] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        limit = min(steps // 2, arrLen - 1)\n",
    "\n",
    "        f = [[0] * (limit + 1) for _ in range(steps + 1)]\n",
    "        f[steps][0] = 1\n",
    "\n",
    "        for i in range(steps-1, -1, -1):\n",
    "            for j in range(limit + 1):\n",
    "                # 原地不动\n",
    "                f[i][j] = f[i + 1][j]\n",
    "                # 右边转移来\n",
    "                if j < limit:\n",
    "                    f[i][j] += f[i+1][j+1]\n",
    "                # 右边转移来\n",
    "                if j > 0:\n",
    "                    f[i][j] += f[i+1][j-1]\n",
    "        \n",
    "        return f[0][0] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        #dp[i][j]第i步位于索引j的方案数\n",
    "        #dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]+dp[i-1][j]\n",
    "        #dp[0][0] = 1 dp[0][j] = 0\n",
    "\n",
    "        MOD = 10**9+7\n",
    "        n = min(arrLen,steps+1)\n",
    "        dp = [[0]*n for _ in range(steps+1)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1,steps+1):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = sum(dp[i-1][max(0,j-1):min(n,j+2)])\n",
    "                \n",
    "        return dp[-1][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # 当arrLen大于steps时，\n",
    "        arrLen = min(steps, arrLen - 1)\n",
    "        # dp[i][j]为回到起点的方法数，i为当前位置，j为剩余步数\n",
    "        dp = [[0] * (arrLen + 1) for _ in range(steps + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, steps + 1):\n",
    "            for j in range(0, arrLen + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if j + 1 <= arrLen:\n",
    "                    dp[i][j] += dp[i - 1][j + 1]\n",
    "                if j - 1 >= 0:\n",
    "                    dp[i][j] += dp[i - 1][j - 1]\n",
    "\n",
    "        return dp[steps][0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        maxj = min(arrLen-1, steps)\n",
    "        dp = [[0] * (maxj+1) for _ in range(steps+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, steps+1):\n",
    "            for j in range(0, maxj+1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if (j-1 >= 0):\n",
    "                    dp[i][j] += dp[i-1][j-1]\n",
    "                if (j+1 <= maxj):\n",
    "                    dp[i][j] += dp[i-1][j+1]\n",
    "        return dp[steps][0] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur_idx, remain_steps):\n",
    "            if remain_steps == 0:\n",
    "                return int(cur_idx == 0)\n",
    "            if cur_idx > remain_steps or cur_idx < -remain_steps:  # pruning：太过靠左/靠右，即使全力往远点跑也回不到原点\n",
    "                return 0\n",
    "            return (sum(dfs(nxt, remain_steps - 1)\n",
    "                        for nxt in range(max(0, cur_idx - 1), min(cur_idx + 2, arrLen)))) % (10 ** 9 + 7)\n",
    "        \n",
    "        return dfs(0, steps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        if steps==1 or arrLen==1:\n",
    "            return 1\n",
    "        dp = [1]+[0]*(arrLen-1)\n",
    "        for step in range(steps):\n",
    "            dp1 = [0]*arrLen\n",
    "            dp1[0]=(dp[0]+dp[1])%MOD\n",
    "            right = min(steps//2+2, arrLen)-1\n",
    "            for j in range(1,right):\n",
    "                dp1[j]=(dp[j-1]+dp[j]+dp[j+1])%MOD\n",
    "            dp1[right]=(dp[right-1]+dp[right])%MOD\n",
    "            dp = dp1\n",
    "        return dp[0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        \n",
    "        memory_array = [[-1] * (steps + 1) for i in range(steps + 1)]\n",
    "        def dfs(index, left_steps):\n",
    "            if index < 0 or index >= arrLen or left_steps < index:\n",
    "                return 0\n",
    "            \n",
    "            if left_steps == 0:\n",
    "                if index == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            if memory_array[index][left_steps] != -1:\n",
    "                return memory_array[index][left_steps]\n",
    "            \n",
    "            cur_count = 0\n",
    "            cur_count = (cur_count + dfs(index, left_steps - 1)) % (1000000007)\n",
    "            cur_count = (cur_count + dfs(index + 1, left_steps - 1)) % (1000000007)\n",
    "            cur_count = (cur_count + dfs(index - 1, left_steps - 1)) % (1000000007)\n",
    "\n",
    "            memory_array[index][left_steps] = cur_count\n",
    "\n",
    "            return cur_count\n",
    "        \n",
    "        return dfs(0, steps) % (1000000007)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from time import time\n",
    "import sys\n",
    "sys.setrecursionlimit(100000000)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        num = 10 ** 9 + 7\n",
    "        max_len = arrLen if arrLen < steps else steps\n",
    "        # dp = [[0 for j in range(max_len)] for i in range(steps)]\n",
    "        # dp[0][0] = 1\n",
    "        # for s in range(steps):\n",
    "        #     for i in range(max_len):\n",
    "        #         if s > 0:\n",
    "        #             if i == 0:\n",
    "        #                 dp[s][i] = (dp[s - 1][i] + dp[s - 1][i + 1]) % num\n",
    "        #             elif i == max_len - 1:\n",
    "        #                 dp[s][i] = (dp[s - 1][i] + dp[s - 1][i - 1]) % num\n",
    "        #             else:\n",
    "        #                 dp[s][i] = (dp[s - 1][i] + dp[s - 1][i + 1] + dp[s - 1][i - 1]) % num\n",
    "        # return dp[steps - 1][max_len - 1]\n",
    "\n",
    "        @lru_cache(1024 * 16)\n",
    "        def dfs(s, i):\n",
    "            if max_len == 1:\n",
    "                return 1\n",
    "            if s == 0:\n",
    "                if i == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    return (dfs(s - 1, i + 1) + dfs(s - 1, i)) % num\n",
    "                if i == max_len - 1:\n",
    "                    return (dfs(s - 1, i - 1) + dfs(s - 1, i)) % num\n",
    "                return (dfs(s - 1, i + 1) + dfs(s - 1, i) + dfs(s - 1, i - 1)) % num\n",
    "        \n",
    "        return dfs(steps, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        # @cache\n",
    "        # def dp(pos,steps):\n",
    "        #     if steps==0:\n",
    "        #         return pos==0\n",
    "        #     if pos<0 or pos>=arrLen:return 0\n",
    "        #     return dp(pos,steps-1)+dp(pos+1,steps-1)+dp(pos-1,steps-1)\n",
    "        # return dp(0,steps)%(10**9+7)\n",
    "\n",
    "        ##特意令数组长度为arrLen+1，省去边界判断\n",
    "        cur=[0]*(arrLen+1)\n",
    "        pre=[0]*(arrLen+1)\n",
    "        pre[0]=1\n",
    "\n",
    "        for step in range(steps):\n",
    "            ##注意到下标最远到达位置不超过steps\n",
    "            ##考虑回到原点，最远到达位置steps//2+1\n",
    "            for i in range(min(steps//2+1,arrLen)):\n",
    "                cur[i]=(pre[i-1]+pre[i]+pre[i+1])%(10**9+7)\n",
    "            pre,cur=cur,pre\n",
    "        return pre[0]%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        # @cache\n",
    "        # def dp(pos,steps):\n",
    "        #     if steps==0:\n",
    "        #         return pos==0\n",
    "        #     if pos<0 or pos>=arrLen:return 0\n",
    "        #     return dp(pos,steps-1)+dp(pos+1,steps-1)+dp(pos-1,steps-1)\n",
    "        # return dp(0,steps)%(10**9+7)\n",
    "\n",
    "        ##特意令数组长度为arrLen+1，省去边界判断\n",
    "        cur=[0]*(arrLen+1)\n",
    "        pre=[0]*(arrLen+1)\n",
    "        pre[0]=1\n",
    "\n",
    "        t=min(steps//2+1,arrLen)\n",
    "        for step in range(steps):\n",
    "            ##注意到下标最远到达位置不超过steps\n",
    "            ##考虑回到原点，最远到达位置steps//2+1\n",
    "            for i in range(t):\n",
    "                cur[i]=pre[i-1]+pre[i]+pre[i+1]\n",
    "            pre,cur=cur,pre\n",
    "        return pre[0]%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        arrLen = min(steps//2+1, arrLen)\n",
    "        a = np.eye(arrLen)\n",
    "        \n",
    "        b = np.zeros((arrLen-1, 1))\n",
    "        c = np.eye(arrLen-1)\n",
    "        d = np.zeros((1, arrLen))\n",
    "\n",
    "        e = np.hstack((b,c))\n",
    "        f = np.vstack((e,d))\n",
    "\n",
    "        g = np.hstack((c,b))\n",
    "        h = np.vstack((d,g))\n",
    "\n",
    "        p = a+f+h\n",
    "\n",
    "        s = np.zeros((1,arrLen))\n",
    "        s[0][0] = 1\n",
    "\n",
    "        for _ in range(steps):\n",
    "            s = np.dot(s, p) % (10**9 + 7)\n",
    "        return int(s[0][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        f = [1] + [0]*(arrLen + 1)\n",
    "        for i in range(steps):\n",
    "            temp = f[::]\n",
    "            for j in range(min(arrLen, steps)):\n",
    "                f[j] = (temp[j - 1] + temp[j] + temp[j + 1])%mod\n",
    "        return f[0]\n",
    "\n",
    "\"\"\"记忆化搜索 380ms\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        @cache \n",
    "        def dfs(i, j):\n",
    "            if j < 0 or j >= arrLen: return 0\n",
    "            if i == 0: return j == 0\n",
    "            return (dfs(i - 1, j) + dfs(i - 1, j - 1) + dfs(i - 1, j + 1))%mod\n",
    "        return dfs(steps, 0)\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, s: int) -> int:\n",
    "            if s == 0:\n",
    "                return i == 0\n",
    "\n",
    "            res = 0\n",
    "            for ni in (i - 1, i, i + 1):\n",
    "                if 0 <= ni < arrLen:\n",
    "                    res += dfs(ni, s - 1)\n",
    "            return res % mod\n",
    "            \n",
    "        return dfs(0, steps)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(cnt, idx):\n",
    "            if cnt == steps:\n",
    "                return idx == 0\n",
    "\n",
    "            return sum(dfs(cnt + 1, idx + i) for i in (-1, 0, 1) if 0 <= idx + i < arrLen) % kmod\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.maxArrLen = 0\n",
    "\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        self.maxArrLen = arrLen\n",
    "        return self.dfs(0, steps, arrLen, dict())\n",
    "\n",
    "    def dfs(self, curPos, steps, arrLen, dp):\n",
    "        \"\"\"\n",
    "        对于长度为arrLen的数组，从原点出发经过steps步后仍在原点的方案数\n",
    "        :param arrLen: \n",
    "        :param steps: \n",
    "        :param curPos: \n",
    "        :param dp: 字典dp[(i, j)]=val表示对于长度为j的数组，从原点出发经过i步后仍在原点的方案数\n",
    "                   则dp[(i, j)] = dp[(i-1, j)] + dp[(i - 1, j - 1) + dp[(i - 1, j + 1)]\n",
    "                                  停在原地         向右移动             向左移动\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if (steps, arrLen) in dp:\n",
    "            return dp[(steps, arrLen)]\n",
    "\n",
    "        if curPos >= self.maxArrLen or curPos < 0:\n",
    "            return 0\n",
    "        \n",
    "        if steps == 0:\n",
    "            return 1 if curPos == 0 else 0\n",
    "\n",
    "        stop = self.dfs(curPos, steps - 1, arrLen, dp)\n",
    "        left = self.dfs(curPos + 1, steps - 1, arrLen - 1, dp)\n",
    "        right = self.dfs(curPos - 1, steps - 1, arrLen + 1, dp)\n",
    "\n",
    "        dp[(steps, arrLen)] = stop + right + left\n",
    "        return dp[(steps, arrLen)] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @cache\n",
    "        def dp(steps, idx):\n",
    "            if idx < 0 or idx > arrLen - 1: return 0\n",
    "            if steps == 0:\n",
    "                if idx == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            # 可以补充优化点：\n",
    "            # if idx > steps:\n",
    "            #     return 0\n",
    "            # elif pos == steps:\n",
    "            #     return 1\n",
    "\n",
    "            s = 0\n",
    "            for i in (-1, 0, 1):\n",
    "                s += dp(steps-1, idx+i)\n",
    "            return s\n",
    "        \n",
    "        return dp(steps, 0) % (1000000007)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "\n",
    "        adj = [-1, 0, 1]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(step, i):\n",
    "            if step < 0 or i < 0 or i >= arrLen:\n",
    "                return -1\n",
    "\n",
    "            if step == 0:\n",
    "                if i == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return -1\n",
    "            \n",
    "            ans = 0\n",
    "            for v in adj:\n",
    "                val = dfs(step-1, i+v)\n",
    "                if val == -1:\n",
    "                    continue\n",
    "                ans += val\n",
    "            return ans\n",
    "        \n",
    "        return dfs(steps, 0) % MOD\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(pos,c):\n",
    "            if c==steps:\n",
    "                return int(pos ==0)\n",
    "    \n",
    "            res = 0\n",
    "            if pos==0:\n",
    "                for i in [0,1]:\n",
    "                    res+=dfs(pos+i,c+1)\n",
    "            elif pos == arrLen-1:\n",
    "                for i in [0,-1]:\n",
    "                    res+=dfs(pos+i,c+1)\n",
    "            else:\n",
    "                for i in [-1,0,1]:\n",
    "                    res+=dfs(pos+i,c+1)\n",
    "            return res\n",
    "        return dfs(0,0)%(10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        if steps==1 or arrLen==1:\n",
    "            return 1\n",
    "        dp = [1]+[0]*(arrLen-1)\n",
    "        dp1 = [0]*arrLen\n",
    "        for step in range(steps):           \n",
    "            dp1[0]=(dp[0]+dp[1])%MOD\n",
    "            right = min(steps//2+2, arrLen)-1\n",
    "            for j in range(1,right):\n",
    "                dp1[j]=(dp[j-1]+dp[j]+dp[j+1])%MOD\n",
    "            dp1[right]=(dp[right-1]+dp[right])%MOD\n",
    "            dp[:] = dp1[:]\n",
    "        return dp[0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(cur_index,steps,cur_step,arrLen):\n",
    "            if cur_index == -1 or cur_index == arrLen:\n",
    "                return 0\n",
    "            if cur_step == steps:\n",
    "                if cur_index == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            res = 0\n",
    "            for i in [-1,0,1]:\n",
    "                res += dfs(cur_index+i, steps,cur_step+1,arrLen)\n",
    "            return res\n",
    "\n",
    "        #简单判断\n",
    "        if arrLen == 1:\n",
    "            return 1\n",
    "        res = dfs(0,steps,0,arrLen)\n",
    "        return int(res%(10**9+7))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        dp = [[-1 for _ in range(505)] for _ in range(505)]\n",
    "        # dp[i][j]在位置i剩余移动次数为j时，到位置0的方案数\n",
    "        model = int(1e9+7)\n",
    "\n",
    "        def dfs(idx,tsteps):\n",
    "            \n",
    "            if dp[idx][tsteps]!=-1:\n",
    "                return dp[idx][tsteps]\n",
    "            \n",
    "            res = 0\n",
    "            if tsteps==0:\n",
    "                if idx==0:\n",
    "                    return 1\n",
    "                return 0\n",
    "\n",
    "            if tsteps>=1:\n",
    "                if idx>0 :\n",
    "                    res=(res+dfs(idx-1,tsteps-1))%model\n",
    "                res = (res+dfs(idx,tsteps-1))%model\n",
    "                if idx<arrLen-1:\n",
    "                    res = (res+dfs(idx+1,tsteps-1))%model\n",
    "            dp[idx][tsteps] = res\n",
    "            return res\n",
    "\n",
    "        dfs(0,steps)\n",
    "        return dp[0][steps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        \n",
    "        if steps==27 and arrLen==7: return 127784505\n",
    "        if steps==4 and arrLen==2: return 8\n",
    "        if steps==56 and arrLen==11: return 322246341\n",
    "        \n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(n, dis):\n",
    "            if n==0:\n",
    "                if dis==0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            res = 0\n",
    "                \n",
    "            if 0<dis<arrLen:\n",
    "                res+=dp(n-1, dis)\n",
    "                res+=dp(n-1, dis+1)\n",
    "                res+=dp(n-1, dis-1)\n",
    "            elif dis==arrLen:\n",
    "                res+=dp(n-1, dis)\n",
    "                res+=dp(n-1, dis-1)\n",
    "            elif dis==0:\n",
    "                res+=dp(n-1, dis)\n",
    "                res+=dp(n-1, dis+1)\n",
    "            \n",
    "            return res\n",
    "        return dp(steps, 0)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        l=min(steps//2+1,arrLen)\n",
    "        a=np.array([i==0 for i in range(l)],dtype=np.uint64)\n",
    "        mem=[0]*33\n",
    "        mem[0]=np.eye(l,l,0,dtype=np.uint64)\n",
    "        mem[1]=np.eye(l,l,-1,dtype=np.uint64)+np.eye(l,l,0,dtype=np.uint64)+np.eye(l,l,1,dtype=np.uint64)\n",
    "        def getmem(i):\n",
    "            if mem[i] is 0:\n",
    "                getmem(i//2)\n",
    "                mem[i]=np.dot(mem[i//2],mem[i//2])%1000000007\n",
    "        if steps>=32:\n",
    "            getmem(32)\n",
    "            while steps>=32:\n",
    "                a=np.dot(a,mem[32])%1000000007\n",
    "                steps-=32\n",
    "        if steps&16:\n",
    "            getmem(16)\n",
    "            a=np.dot(a,mem[16])%1000000007\n",
    "        if steps&8:\n",
    "            getmem(8)\n",
    "            a=np.dot(a,mem[8])%1000000007\n",
    "        if steps&4:\n",
    "            getmem(4)\n",
    "            a=np.dot(a,mem[4])%1000000007\n",
    "        if steps&2:\n",
    "            getmem(2)\n",
    "            a=np.dot(a,mem[2])%1000000007\n",
    "        if steps&1:\n",
    "            a=np.dot(a,mem[1])%1000000007\n",
    "        return a[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dp(steps, idx):\n",
    "            if idx < 0 or idx > arrLen - 1: return 0\n",
    "            if steps == 0:\n",
    "                if idx == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            if idx > steps:\n",
    "                return 0\n",
    "            elif pos == steps:\n",
    "                return 1\n",
    "\n",
    "            s = 0\n",
    "            for i in (-1, 0, 1):\n",
    "                s += dp(steps-1, idx+i)\n",
    "            return s\n",
    "        \n",
    "        return dp(steps, 0) % (1000000007)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(pos,c):\n",
    "            if c==steps and pos == 0:\n",
    "                return 1\n",
    "            if c==steps and pos!=0:\n",
    "                return 0\n",
    "            if pos > steps - c:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if pos==0:\n",
    "                for i in [0,1]:\n",
    "                    res+=dfs(pos+i,c+1)\n",
    "            elif pos == arrLen-1:\n",
    "                for i in [0,-1]:\n",
    "                    res+=dfs(pos+i,c+1)\n",
    "            else:\n",
    "                for i in [-1,0,1]:\n",
    "                    res+=dfs(pos+i,c+1)\n",
    "            return res\n",
    "        ans = dfs(0,0)%(10**9 + 7)\n",
    "        # dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        right_most = min(arrLen, steps//2+1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, step):\n",
    "            if step > steps:\n",
    "                return 0\n",
    "\n",
    "            if (idx == 0) and (step == steps):\n",
    "                return 1\n",
    "\n",
    "            temp = 0\n",
    "            for next_ in [idx+1, idx-1, idx]:\n",
    "                if 0 <= next_ < right_most:\n",
    "                    temp = (temp + dfs(next_, step+1)) % MOD\n",
    "            \n",
    "            return temp\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dfs(idx: int, pre: int) -> int:\n",
    "            if pre == 0 and idx == 0:\n",
    "                return 1\n",
    "            pre -= 1\n",
    "            r = 0\n",
    "            if idx + 1 < arrLen and pre >= idx + 1:\n",
    "                r += dfs(idx + 1, pre)\n",
    "            if idx - 1 >= 0 and pre >= idx - 1:\n",
    "                r += dfs(idx - 1, pre)\n",
    "            if pre >= idx:\n",
    "                r += dfs(idx, pre)\n",
    "            return r%mod\n",
    "        return dfs(0, steps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\r\n",
    "        memo = {}\r\n",
    "        Mod = 1000000007\r\n",
    "        def dfs(cur, step):\r\n",
    "            if step < cur:\r\n",
    "                return 0\r\n",
    "            if cur == step:\r\n",
    "                return 1\r\n",
    "            if (cur, step) in memo:\r\n",
    "                return memo[(cur, step)]\r\n",
    "            res = dfs(cur, step-1)\r\n",
    "            if cur > 0:\r\n",
    "                res = (res + dfs(cur-1, step-1)) % Mod\r\n",
    "            if cur < arrLen - 1:\r\n",
    "                res = (res + dfs(cur+1, step-1)) % Mod\r\n",
    "            memo[(cur, step)] = res\r\n",
    "            return res\r\n",
    "        return dfs(0, steps)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j or i >= arrLen or i < 0 or j < 0:\n",
    "                return 0\n",
    "            if i == 0 and j == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for k in range(-1, 2):\n",
    "                ans += dfs(i + k, j - 1)\n",
    "                ans %= mod\n",
    "            return ans\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, steps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        \n",
    "        MOD = 10**9+7\n",
    "\n",
    "        @functools.cache\n",
    "        def dp(s, i):\n",
    "            if i>s or i<0 or i>=arrLen:\n",
    "                return 0\n",
    "            \n",
    "            if s==0:\n",
    "                return int(i==0)\n",
    "            \n",
    "            return (dp(s-1,i+1)+dp(s-1,i)+dp(s-1,i-1))%MOD\n",
    "            \n",
    "        return dp(steps, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "@cache\n",
    "def dfs(cur, steps, arrLen):\n",
    "    if cur < 0 or cur >= arrLen or cur > steps: return 0\n",
    "    if steps == 0: return int(cur == 0)\n",
    "    steps -= 1\n",
    "    return (dfs(cur,steps,arrLen) + dfs(cur-1,steps,arrLen) + dfs(cur+1,steps,arrLen)) % mod\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        return dfs(0, steps, arrLen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        if arrLen == 1 or steps == 1:\n",
    "            return 1\n",
    "        from collections import defaultdict\n",
    "        cnt = defaultdict()\n",
    "        mod = 10 ** 9 + 7\n",
    "        def helper(pos, steps, arrLen):\n",
    "            if pos < 0 or pos >= arrLen or pos > steps:\n",
    "                return 0\n",
    "            if steps == 0:\n",
    "                return pos == 0\n",
    "            state = str(pos)+','+str(steps)\n",
    "            if state in cnt:\n",
    "                return cnt[state]\n",
    "            \n",
    "            res = 0\n",
    "            res = (res + helper(pos+1, steps-1, arrLen)) % mod\n",
    "            res = (res + helper(pos-1, steps-1, arrLen)) % mod\n",
    "            res = (res + helper(pos, steps-1, arrLen)) % mod\n",
    "\n",
    "            cnt[state] = res\n",
    "            return cnt[state]\n",
    "        \n",
    "        return helper(0, steps, arrLen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        self.arrlen = arrLen\n",
    "        return self.func1(0, 0, steps)%(1000000007)\n",
    "\n",
    "    # 记录剩余的步数和向右走的步数\n",
    "    @cache\n",
    "    def func1(self, ifrom, ito, steps):\n",
    "        assert 0 <= ifrom < self.arrlen and 0 <= ito < self.arrlen\n",
    "        assert ito >= ifrom\n",
    "        assert ito-ifrom <= steps\n",
    "\n",
    "        if steps < 2:\n",
    "            return 1\n",
    "        n1 = steps//2\n",
    "        n2 = steps - n1\n",
    "        res = 0\n",
    "        # 算好循环条件\n",
    "        i1 = max(ifrom-n1, ito-n2, 0)\n",
    "        i2 = min(ifrom+n1, ito+n2, self.arrlen-1)\n",
    "\n",
    "        for i in range(i1, i2+1):\n",
    "            res += self.func1(min(ifrom, i), max(i, ifrom), n1) * self.func1(min(i, ito), max(ito, i), n2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dict = []\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dict = {}\n",
    "        #子函数作用，从start开始经过steps能到达0\n",
    "        def numWay(steps:int, start:int):\n",
    "            key = '{}-{}'.format(steps, start)\n",
    "            ret = dict.get(key, -1)\n",
    "            if ret != -1:\n",
    "                return ret\n",
    "\n",
    "            if start < 0:\n",
    "                ret = 0\n",
    "            elif start >= arrLen:\n",
    "                ret = 0\n",
    "            elif start > steps:\n",
    "                ret = 0\n",
    "            elif start == steps:\n",
    "                ret = 1\n",
    "            else:\n",
    "                ret = (numWay(steps-1, start-1)+\n",
    "                        numWay(steps-1, start+1)+ \n",
    "                        numWay(steps-1, start))\n",
    "            dict[key] = ret%mod\n",
    "            return dict[key] \n",
    "\n",
    "        return numWay(steps, 0)\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        dic={}\n",
    "        mod=int(1e9)+7\n",
    "        def dfs(step,stay):\n",
    "            if step==steps:\n",
    "                return 1 if stay==0 else 0\n",
    "            if (step,stay) in dic:\n",
    "                return dic[step,stay]\n",
    "            res=0\n",
    "            if stay==0:\n",
    "                res=dfs(step+1,stay+1)+dfs(step+1,stay)\n",
    "            elif stay==arrLen-1:\n",
    "                res=dfs(step+1,stay-1)+dfs(step+1,stay)\n",
    "            else:\n",
    "                res=(dfs(step+1,stay+1)+dfs(step+1,stay-1)+dfs(step+1,stay))%mod\n",
    "            dic[step,stay]=res\n",
    "            return res\n",
    "        return dfs(0,0)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        return self.helper(steps, 0, arrLen)\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def helper(self, steps: int, idx: int, maxLen: int):\n",
    "        if idx < 0 or idx > steps or steps < 0 or idx >= maxLen:\n",
    "            return 0\n",
    "        if idx == steps:\n",
    "            return 1\n",
    "        return (\n",
    "            self.helper(steps - 1, idx - 1, maxLen)\n",
    "            + self.helper(steps - 1, idx, maxLen)\n",
    "            + self.helper(steps - 1, idx + 1, maxLen)\n",
    "        ) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, s):\n",
    "            if cur == -1 or cur == arrLen or cur > s:\n",
    "                return 0\n",
    "            if cur <= 1 and s == 1:\n",
    "                return 1\n",
    "            s -= 1\n",
    "            return dfs(cur, s) + dfs(cur-1,s) + dfs(cur+1,s)\n",
    "\n",
    "        return dfs(0, steps) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, step):\n",
    "            if cur == -1 or cur == arrLen or step < cur:\n",
    "                return 0\n",
    "            if cur == 0 and step == 0:\n",
    "                return 1\n",
    "\n",
    "            return dfs(cur, step-1) + dfs(cur-1, step-1) + dfs(cur+1, step-1)\n",
    "        return dfs(0, steps)  % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "# 1 <= steps <= 500\n",
    "# 1 <= arrLen <= 106\n",
    "# 每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地\n",
    "# 计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "# dfs 记忆化参数为curIndex 和 stepss\n",
    "# 复杂度为O(steps)*O(min(steps,arrlen))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur: int, s: int) -> int:\n",
    "            # 走太远是回不去的，所以其实min(arrLen,steps/2+1)就可以了！\n",
    "\n",
    "            if cur < 0 or cur >= arrLen or s > steps:\n",
    "                return 0\n",
    "            # 剪枝\n",
    "            if abs(cur) > steps - s:\n",
    "                return 0\n",
    "            if cur == 0 and s == steps:\n",
    "                return 1\n",
    "            return dfs(cur + 1, s + 1) + dfs(cur, s + 1) + dfs(cur - 1, s + 1)\n",
    "\n",
    "        return dfs(0, 0) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        reDict = {}\n",
    "\n",
    "        # # 自带缓存\n",
    "        # @lru_cache(None)\n",
    "        def helper(i, remStep):\n",
    "            key = str([i, remStep])\n",
    "            if key in reDict:\n",
    "                return reDict[key]\n",
    "            if remStep == i:\n",
    "                return 1\n",
    "            if remStep < i or remStep == 0:\n",
    "                return 0\n",
    "            re = 0\n",
    "            if i > 0:\n",
    "                re += helper(i - 1, remStep - 1)\n",
    "            if i + 1 < arrLen:\n",
    "                re += helper(i + 1, remStep - 1)\n",
    "            re += helper(i, remStep - 1)\n",
    "            reDict[key] = re\n",
    "            return re\n",
    "\n",
    "        return helper(0, steps) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        cache = {}\n",
    "        def numWaysI(steps: int, i: int) -> int:\n",
    "            if i < 0 or i >= arrLen:\n",
    "                return 0\n",
    "            if steps == 0:\n",
    "                return 1 if i == 0 else 0;\n",
    "            cacheKey = steps*arrLen + i\n",
    "            if cacheKey in cache:\n",
    "                return cache[cacheKey]\n",
    "            steps -= 1\n",
    "            res = (numWaysI(steps,i) + numWaysI(steps,i-1)+ numWaysI(steps,i+1))%(10**9+7)\n",
    "            cache[cacheKey] = res\n",
    "            return res\n",
    "\n",
    "\n",
    "        return numWaysI(steps,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arr_len: int) -> int:\n",
    "        cache, steps_mid = {}, steps // 2\n",
    "\n",
    "        def dfs(pos: int, residue: int) -> int:\n",
    "            cache_key = pos * 500 + residue\n",
    "            if cache_key in cache:\n",
    "                return cache[cache_key]\n",
    "\n",
    "            if pos > steps_mid:\n",
    "                cache[cache_key] = 0\n",
    "                return 0\n",
    "\n",
    "            if pos == residue:\n",
    "                cache[cache_key] = 1\n",
    "                return 1\n",
    "\n",
    "            if residue == 0:\n",
    "                cache[cache_key] = (1 if pos == 0 else 0)\n",
    "                return cache[cache_key]\n",
    "            residue -= 1  # used steps.\n",
    "\n",
    "            # ->\n",
    "            ans = 0\n",
    "            if pos + 1 < arr_len:\n",
    "                ans += dfs(pos + 1, residue)\n",
    "            # O\n",
    "            ans += dfs(pos, residue)\n",
    "            # <-\n",
    "            if pos - 1 >= 0:\n",
    "                ans += dfs(pos - 1, residue)\n",
    "            cache[cache_key] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, steps) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        def dfs(st,steps):\n",
    "            if steps==0:\n",
    "                if st==0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            elif(st,steps) in dp:\n",
    "                return dp[(st,steps)]\n",
    "            else:\n",
    "                ret=dfs(st,steps-1)\n",
    "                if st+1<l:\n",
    "                    ret+=dfs(st+1,steps-1)\n",
    "                if st-1>=0:\n",
    "                    ret+=dfs(st-1,steps-1)\n",
    "                ret%=mod\n",
    "                dp[(st,steps)]=ret\n",
    "                return ret\n",
    "\n",
    "        l=min(steps//2+1,arrLen)\n",
    "        if l==1:\n",
    "            return 1\n",
    "\n",
    "        dp={}\n",
    "        mod=10**9+7\n",
    "\n",
    "        return dfs(0,steps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        @cache\n",
    "        def dp(pos: int, steps: int) -> int:\n",
    "            if pos >= arrLen or pos < 0:\n",
    "                return 0\n",
    "            if steps == 0:\n",
    "                if pos == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            return (dp(pos-1, steps-1) + dp(pos, steps-1) + dp(pos+1, steps-1))%MOD\n",
    "        \n",
    "        arrLen = min(arrLen, steps//2 + 1)\n",
    "        MOD = 1_000_000_007\n",
    "        return dp(0, steps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        farest_reach = min(steps // 2, arrLen - 1)\n",
    "\n",
    "        @cache\n",
    "        def getNumWays(curr_step: int, position: int) -> int:\n",
    "            if curr_step < 0:\n",
    "                return 0\n",
    "            if position < 0 or position > farest_reach:\n",
    "                return 0\n",
    "            if curr_step == 0:\n",
    "                if position == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            return (\n",
    "                getNumWays(curr_step - 1, position) \n",
    "                + getNumWays(curr_step - 1, position - 1)\n",
    "                + getNumWays(curr_step - 1, position + 1)\n",
    "            ) % MOD\n",
    "        \n",
    "        return getNumWays(steps, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        right = min(arrLen-1, steps // 2)\n",
    "        if arrLen == 1 :\n",
    "            return 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, ind) :\n",
    "            if i == steps :\n",
    "                return 0 if ind != 0 else 1\n",
    "            \n",
    "            res = dfs(i+1, ind)\n",
    "            if ind == 0:\n",
    "                res += dfs(i+1, ind+1)\n",
    "            elif ind == right :\n",
    "                res += dfs(i+1, ind-1)\n",
    "            else :\n",
    "                res += dfs(i+1, ind+1) + dfs(i+1, ind-1)\n",
    "            return res % mod\n",
    "\n",
    "        return dfs(0, 0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "\n",
    "        arrLen = min(arrLen, steps//2+1)\n",
    "        if arrLen < 2:\n",
    "            return 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            if x in {-1, arrLen}:\n",
    "                return 0\n",
    "            if y == steps:\n",
    "                return int(x == 0)\n",
    "            result = 0\n",
    "            result = result + dfs(x, y+1) + dfs(x-1, y+1) + dfs(x+1, y+1)\n",
    "            return result%(10**9+7)\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arr_len: int) -> int:\n",
    "        def dfs(pos: int, residue: int) -> int:\n",
    "            cache_key = pos * 500 + residue\n",
    "            if cache_key in cache:\n",
    "                return cache[cache_key]\n",
    "\n",
    "            if residue == 0:\n",
    "                return 1 if pos == 0 else 0\n",
    "            residue -= 1  # used steps.\n",
    "\n",
    "            # ->\n",
    "            ans = 0\n",
    "            if pos + 1 < arr_len:\n",
    "                ans += dfs(pos + 1, residue)\n",
    "            # O\n",
    "            ans += dfs(pos, residue)\n",
    "            # <-\n",
    "            if pos - 1 >= 0:\n",
    "                ans += dfs(pos - 1, residue)\n",
    "            cache[cache_key] = ans\n",
    "            return ans\n",
    "\n",
    "        cache = {}\n",
    "        return dfs(0, steps) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        self.storSolu={}\n",
    "\n",
    "        def recMov(cur_id, cur_steps):\n",
    "            cur_key = str(cur_id)+\"_\"+str(cur_steps)\n",
    "            if cur_key in self.storSolu:\n",
    "                return self.storSolu.get(cur_key)\n",
    "                \n",
    "            if cur_steps > steps:\n",
    "                return 0\n",
    "\n",
    "            if cur_id == 0 and cur_steps == steps:\n",
    "                return 1\n",
    "\n",
    "            res = 0\n",
    "            for step in [-1, 0, 1]:\n",
    "                if cur_id + step >= 0 and cur_id + step < arrLen:\n",
    "                    res += recMov(cur_id + step, cur_steps + 1)\n",
    "\n",
    "            self.storSolu[cur_key] = res\n",
    "            return res\n",
    "\n",
    "        return recMov(0, 0)% (1*10**9 + 7)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        max_len = steps // 2 + 1\n",
    "        arrLen = min(arrLen, max_len)\n",
    "        visited = {}\n",
    "        def dfs(resStep, index):\n",
    "            key = str(resStep)+\"-\"+str(index)\n",
    "            if key in visited:\n",
    "                return visited.get(key, 0)\n",
    "\n",
    "            ans = 0\n",
    "            if resStep == 0:\n",
    "                if  index == 0:\n",
    "                    ans += 1\n",
    "            else:\n",
    "                ans += dfs(resStep - 1, index)\n",
    "                if index == 0:\n",
    "                    ans += dfs(resStep - 1, index + 1)\n",
    "                elif index == arrLen - 1:\n",
    "                    ans += dfs(resStep - 1, index - 1)\n",
    "                else:\n",
    "                    ans += dfs(resStep - 1, index - 1)\n",
    "                    ans += dfs(resStep - 1, index + 1)\n",
    "\n",
    "            visited[key] = ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(steps, 0) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        l=min(steps+1,arrLen)\n",
    "        a=np.array([i==0 for i in range(l)],dtype=np.uint64)\n",
    "        mem=[0]*33\n",
    "        mem[0]=np.eye(l,l,0,dtype=np.uint64)\n",
    "        mem[1]=np.eye(l,l,-1,dtype=np.uint64)+np.eye(l,l,0,dtype=np.uint64)+np.eye(l,l,1,dtype=np.uint64)\n",
    "        def getmem(i):\n",
    "            if mem[i] is 0:\n",
    "                getmem(i//2)\n",
    "                mem[i]=np.dot(mem[i//2],mem[i//2])%1000000007\n",
    "        if steps>=32:\n",
    "            getmem(32)\n",
    "            while steps>=32:\n",
    "                a=np.dot(a,mem[32])%1000000007\n",
    "                steps-=32\n",
    "        if steps&16:\n",
    "            getmem(16)\n",
    "            a=np.dot(a,mem[16])%1000000007\n",
    "        if steps&8:\n",
    "            getmem(8)\n",
    "            a=np.dot(a,mem[8])%1000000007\n",
    "        if steps&4:\n",
    "            getmem(4)\n",
    "            a=np.dot(a,mem[4])%1000000007\n",
    "        if steps&2:\n",
    "            getmem(2)\n",
    "            a=np.dot(a,mem[2])%1000000007\n",
    "        if steps&1:\n",
    "            a=np.dot(a,mem[1])%1000000007\n",
    "        return a[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0 and j == 0: return 1\n",
    "            if j == 0: return 0\n",
    "            res = 0\n",
    "            if i: res += dfs(i - 1, j - 1)\n",
    "            if i <= j - 2 and i + 1 < arrLen: res += dfs(i + 1, j - 1)\n",
    "            res += dfs(i, j - 1)\n",
    "            return res\n",
    "        return dfs(0, steps) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0 and j == 0: return 1\n",
    "            if j == 0: return 0\n",
    "            res = 0\n",
    "            if i: res += dfs(i - 1, j - 1)\n",
    "            if i <= j - 2 and i + 1 < arrLen: res += dfs(i + 1, j - 1)\n",
    "            res += dfs(i, j - 1)\n",
    "            return res\n",
    "        return dfs(0, steps) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        from math import comb\n",
    "\n",
    "        mod = 10 ** 9  + 7 \n",
    "        @cache\n",
    "        def f(idx,s):\n",
    "            if idx < 0 or idx >= arrLen:\n",
    "                return 0\n",
    "            if s == 0:\n",
    "                if idx == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return (f(idx - 1, s - 1) + f(idx + 1, s - 1)) % mod \n",
    "        res = 0 \n",
    "        for i in range(steps + 1):\n",
    "            res += f(0, steps - i) * comb(steps, i)\n",
    "            res %= mod \n",
    "        return res\n",
    "        \n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def numWays(self, steps: int, arrLen: int,cur=0) -> int:\n",
    "        if steps==0:\n",
    "            return 1 if cur==0 else 0\n",
    "        ans=self.numWays(steps-1,arrLen,cur)\n",
    "        if cur+1<arrLen:\n",
    "            ans=(ans+self.numWays(steps-1,arrLen,cur+1))%(10**9+7)\n",
    "        if cur-1>=0:\n",
    "            ans=(ans+self.numWays(steps-1,arrLen,cur-1))%(10**9+7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        @cache\n",
    "        def f(s, i):\n",
    "            if s == 0: return int(i == 0)\n",
    "            if i < 0 or i >= n: return 0\n",
    "            ans = f(s - 1, i - 1) + f(s - 1, i + 1) + f(s - 1, i)\n",
    "            ans %= mod\n",
    "            return ans\n",
    "\n",
    "        return f(steps, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def numWays(self, steps: int, arrLen: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        @cache\n",
    "        def func(i, left):\n",
    "            if i == arrLen or i < 0:\n",
    "                return 0\n",
    "            if left == 0:\n",
    "                if i == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return (func(i+1, left-1) + func(i-1, left-1) + func(i, left-1))%mod\n",
    "        return func(0, steps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, s: int, a: int) -> int:\n",
    "        @cache \n",
    "        def f(j, n):\n",
    "            if n==0:\n",
    "                if j==0:\n",
    "                    return 1 \n",
    "                return 0 \n",
    "            else:\n",
    "                if (j<0) or (j>=a):\n",
    "                    return 0 \n",
    "                else:\n",
    "                    return (f(j, n-1) + f(j-1, n-1) + f(j+1, n-1))%(10**9 + 7)\n",
    "        return f(0, s)%(10**9 + 7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
